一、引入
题目:
给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。
最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。
数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。
输入格式
第一行包含两个整数n和m。
接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
二、思路
搜索树：
用vis【】【】 数组记录某个位置是否访问过。访问过为1，未访问过为0。
用一个结构体代表状态的变化。
三、代码
#include <cstdio>
#include <queue>
using namespace std
;
const int N
= 105;
struct Node
{
int x
, y
, step
;
Node(int x
, int y
, int step
): x(x
), y(y
), step(step
) {}
};
int dx
[4] = {-1, 1, 0, 0};
int dy
[4] = {0, 0, -1, 1};
int g
[N
][N
], n
, m
, vis
[N
][N
];
bool ok(int x
, int y
) {
if (x
< 0 || y
< 0 || x
>= n
|| y
>= m
|| g
[x
][y
] == 1) return false;
return true;
}
int bfs() {
queue
<Node
> q
;
q
.push(Node(0, 0, 0));
vis
[0][0] = 1;
while (!q
.empty()) {
Node t
= q
.front();
q
.pop();
if (t
.x
== n
- 1 && t
.y
== m
- 1) {
return t
.step
;
}
for (int i
= 0; i
< 4; i
++) {
int fx
= t
.x
+ dx
[i
];
int fy
= t
.y
+ dy
[i
];
if (ok(fx
, fy
) && !vis
[fx
][fy
]) {
vis
[fx
][fy
] = 1;
q
.push(Node(fx
, fy
, t
.step
+ 1));
}
}
}
}
int main
() {
scanf("%d%d", &n
, &m
);
for (int i
= 0; i
< n
; i
++) {
for (int j
= 0; j
< m
; j
++) {
scanf("%d", &g
[i
][j
]);
}
}
printf("%d", bfs());
return 0;
}
