下面的程序用广度优先搜索(BFS)在一个 n 行 m 列的 0/1 网格中,求从起点 (sx, sy) 到终点 (tx, ty) 的最短步数。0 表示可通行的格子,1 表示障碍;若终点不可达则输出 -1。队列用数组 qx、qy 配合头指针 head、尾指针 tail 模拟。试补全程序。
#include <cstdio>
int n, m;
int g[105][105], dis[105][105];
int qx[10005], qy[10005];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &g[i][j]);
int sx, sy, tx, ty;
scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
dis[i][j] = -1;
int head = 1, tail = 0;
qx[++tail] = sx;
qy[tail] = sy;
dis[sx][sy] = ___①___;
while (___②___) {
int x = qx[head], y = qy[head];
___③___
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == 0 &&
___④___) {
dis[nx][ny] = dis[x][y] + 1;
qx[++tail] = nx;
___⑤___
}
}
}
printf("%d\n", dis[tx][ty]);
return 0;
}