67 lines
1.7 KiB
C++
67 lines
1.7 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int INF = 0x3f3f3f3f;
|
||
const int N = 51;
|
||
int n, m; //n行m列
|
||
int p, q; //小哈所在的位置
|
||
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
|
||
*/
|
||
int dx[4] = {0, 1, 0, -1};//上,右，下，左
|
||
int dy[4] = {1, 0, -1, 0};
|
||
int tx, ty;
|
||
void dfs(int x, int y, int step) {
|
||
//判断是否到达小哈的位置
|
||
if (x == p && y == q) {
|
||
if (step < Min) Min = step; //更新最小值
|
||
return;
|
||
}
|
||
/*枚举四种走法*/
|
||
for (int i = 0; i <= 3; i++) {
|
||
/*计算下一个点的坐标*/
|
||
tx = x + dx[i], ty = y + dy[i];
|
||
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() {
|
||
//小哼开始的位置
|
||
int sx, sy;
|
||
|
||
cin >> n >> m;
|
||
/*读入迷宫*/
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= m; j++)
|
||
cin >> a[i][j];
|
||
//读入起点和终点坐标
|
||
cin >> sx >> sy >> p >> q;
|
||
|
||
/*从起点开始搜索*/
|
||
st[sx][sy] = true; //标记起点已经在路径中，防止后面重复走
|
||
//第一个参数是起点的x坐标，以此类推是起点的y坐标，初始步数为0
|
||
dfs(sx, sy, 0);
|
||
//输出最短步数
|
||
cout << Min << endl;
|
||
return 0;
|
||
} |