题目描述

走迷宫——DFS算法（解决时间超限）

算法1

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 110;
const int M = 110;
int a[N][M];
bool book[N][M];
int n, m;
int res = N*M;
int f[N][M];


//dfs算法
void dfs(int x, int y, int step)
{
    int ne[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    int i;

    if (step >= f[x][y]) //走过的步数大于上一存储的最小步数，不满足题目要求的最小步数
        return;
    f[x][y] = step;

    if (x == n && y == m) { //到达右下角
        res = min(res, step); //得最小步数
        return;
    }

    int tx, ty;
    for (i = 0; i < 4; i ++) {
        tx = x + ne[i][0];
        ty = y + ne[i][1];

        //判断
        if (tx > 0 && tx <= n && ty > 0 && ty <= m && book[tx][ty] == false && a[tx][ty] == 0) {
            book[tx][ty] = true;
            dfs(tx, ty, step + 1);
            book[tx][ty] = false;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int j = 1; j <= n; ++ j) {
        for (int k = 1; k <= m; ++ k) {
            scanf("%d", &a[j][k]);
            f[j][k] = N*M;
        }
    }

    book[1][1] = true; //源点标记走过
    dfs(1, 1, 0);

    printf("%d\n", res);

    return 0;
}