#include using namespace std; const int INF = 0x3f3f3f3f; const int N = 51; int n, m; // n行m列 int hax, hay; //小哈所在的位置 int hengx, hengy; //小哼开始的位置 int Min = INF; //步骤最小值 int a[N][N]; //地图 bool st[N][N]; //是否走过 /** 测试数据 5 4 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 4 3 */ void dfs(int x, int y, int step) { int dx[4] = {0, 1, 0, -1}; //上,右,下,左 int dy[4] = {1, 0, -1, 0}; int tx, ty, k; //判断是否到达小哈的位置 if (x == hax && y == hay) { if (step < Min) Min = step; //更新最小值 return; } /*枚举四种走法*/ for (k = 0; k <= 3; k++) { /*计算下一个点的坐标*/ tx = x + dx[k]; ty = y + dy[k]; if (tx < 1 || tx > n || ty < 1 || ty > m) //判断是否越界 continue; /*判断该点是否为障碍物或者已经在路径中*/ if (!a[tx][ty] && !st[tx][ty]) { st[tx][ty] = true; //标记这个点已经走过 dfs(tx, ty, step + 1); //开始尝试下一个点 st[tx][ty] = false; //尝试结束,取消这个点的标记 } } } int main() { cin >> n >> m; /*读入迷宫*/ for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; //读入起点和终点坐标 cin >> hengx >> hengy >> hax >> hay; /*从起点开始搜索*/ st[hengx][hengy] = true; //标记起点已经在路径中,防止后面重复走 //第一个参数是起点的x坐标,以此类推是起点的y坐标,初始步数为0 dfs(hengx, hengy, 0); //输出最短步数 cout << Min << endl; return 0; }