本文共 2237 字，大约阅读时间需要 7 分钟。

该问题的解决方法

这个问题可以通过深度优先搜索（DFS）来解决。DFS是一种有效的路径查找算法，因为图中的每个位置都是可以通过检查四个方向来访问的（上下左右）。

关键点

算法步骤

优化技巧

代码实现

以下是优化后的代码实现。主要的改动包括优化剪枝逻辑，并确保正确处理移动步骤。

#include 
   
    using namespace std;int n, m;int x, y, p, q;int a[21][21];int book[21][21];int minn = 999999;string dir[4] = {"up", "down", "left", "right"};void dfs(int tx, int ty, int sum) {    static int visit[21][21];    if (tx < 1 || tx > n || ty < 1 || ty > m)        return;    if (visit[tx][ty])        return;    visit[tx][ty] = 1;    if (tx == p && ty == q) {        if (sum < minn)            minn = sum;        return;    }    int dx, dy;    for (int i = 0; i < 4; ++i) {        if (tx + dir[i][0], ty + dir[i][1])...); // 修改后的移动逻辑    }    return;}int main() {    while (scanf("%d %d", &n, &m) != EOF) {        memset(a, 0, sizeof(a));        memset(book, 0, sizeof(book));        int sx, sy, syx, syy;        for (int i = 1; i <= n; ++i) {            for (int j = 1; j <= m; ++j) {                char c;                scanf("%c", &c);                a[i][j] = c;                if (c == 'X') {                    sx = i;                    sy = j;                } else if (c == 'Y') {                    syx = i;                    syy = j;                }            }        }        if (sx == syx && sy == syy) {            cout << 0 << endl;            continue;        }        dfs(sx, sy, 0);        if (minn != 999999)            cout << minn << endl;        else            cout << "-1" << endl;    }    return 0;}
   

思考

测试

在示例1中：

3 3X#Y

#*#

网格如下：

X # Y

• *

*

代码的输出应该是4秒，因为可以走右边上下移动一组。

在第二个测试案例中，X和Y被障碍物包围，无法到达，输出-1。

转载地址：http://vkexz.baihongyu.com/