题解 | #走迷宫#

首先，若使用回溯的方法会超时，代码如下所示：

#include<iostream>
#include<vector>
#include<queue>
#define INF 1e+7
using namespace std;
typedef struct node {
    int row;
    int col;
    node(int f, int t) :row(f), col(t) {}
}Node;
typedef struct direct {
    int crow;
    int ccol;
    direct(int f, int t) :crow(f), ccol (t) {}
}Direct;
vector<char> vec[1001];
int dp[1001][1001];
Direct dir[4] = { Direct {1,0},Direct{-1,0},Direct{0,1},Direct{0,-1} };
int main()
{
    char c;
    int xs, ys, n, m, xt, yt;
    queue<Node> qu;
    cin >> n >> m;
    cin >> xs >> ys >> xt >> yt;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j)
            dp[i][j] = -1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> c;
            if (vec[i].empty())
                vec[i].push_back('0');
            vec[i].push_back(c);
        }
    }
    qu.push(Node{ xs,ys });
    while (!qu.empty()) {
        Node point = qu.front();
        qu.pop();
        for (int i = 0; i < 4; ++i) {
            int row = point.row + dir[i].crow;
            int col = point.col + dir[i].ccol;
            if (row >= 1 && row <= n && col >= 1 && col <= m && vec[row][col] == '.' && dp[row][col] == -1) {
                qu.push(Node{ row,col });
                dp[row][col] = dp[point.row][point.col] + 1;
            }
        }
    }
    if (dp[xt][yt] != -1)
        cout << ((xt == xs && yt == ys ) ? 0 : dp[xt][yt] + 1);
    else
        cout << -1;
}

运用BFS进行广度搜索(此方法仅用于每两个相连的点的距离都为1)；此外，如果用回溯的方***导致超时。

#include<iostream>
#include<vector>
#include<queue>
#define INF 1e+7
using namespace std;
typedef struct node {
    int row;
    int col;
    node(int f, int t) :row(f), col(t) {}
}Node;
typedef struct direct {
    int crow;
    int ccol;
    direct(int f, int t) :crow(f), ccol (t) {}
}Direct;
vector<char> vec[1001];
int dp[1001][1001];
Direct dir[4] = { Direct {1,0},Direct{-1,0},Direct{0,1},Direct{0,-1} };
int main()
{
    char c;
    int xs, ys, n, m, xt, yt;
    queue<Node> qu;
    cin >> n >> m;
    cin >> xs >> ys >> xt >> yt;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j)
            dp[i][j] = -1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> c;
            if (vec[i].empty())
                vec[i].push_back('0');
            vec[i].push_back(c);
        }
    }
    qu.push(Node{ xs,ys });
    while (!qu.empty()) {
        Node point = qu.front();
        qu.pop();
        for (int i = 0; i < 4; ++i) {
            int row = point.row + dir[i].crow;
            int col = point.col + dir[i].ccol;
            if (row >= 1 && row <= n && col >= 1 && col <= m && vec[row][col] == '.' && dp[row][col] == -1) {
                qu.push(Node{ row,col });
                dp[row][col] = dp[point.row][point.col] + 1;
            }
        }
    }
    if (dp[xt][yt] != -1)
        cout << ((xt == xs && yt == ys ) ? 0 : dp[xt][yt] + 1);
    else
        cout << -1;
}