NYOJ - 最少步数【BFS】

最少步数

描述

这有一个迷宫，有0~8行和0~8列：

 1,1,1,1,1,1,1,1,1
 1,0,0,1,0,0,1,0,1
 1,0,0,1,1,0,0,0,1
 1,0,1,0,1,1,0,1,1
 1,0,0,0,0,1,0,0,1
 1,1,0,1,0,1,0,0,1
 1,1,0,1,0,1,0,0,1
 1,1,0,1,0,0,0,0,1
 1,1,1,1,1,1,1,1,1

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入

第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。

输出

输出最少走几步。

样例输入

2
3 1  5 7
3 1  6 7

样例输出

12
11

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>using namespace std;const int INF = 1000000;
int maze[9][9] = {  // 迷宫地图1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,1,0,1,1,0,0,1,1,0,0,0,1,1,0,1,0,1,1,0,1,1,1,0,0,0,0,1,0,0,1,1,1,0,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,1,1,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1
};
int d[9][9];   // 到各个位置最短距离的数组
int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};  // 4个方向的移动的向量
typedef pair<int , int> P;  // 使用pair表示状态
int sx,sy;   //起点坐标
int gx,gy;   //终点坐标
int BFS(void)
{queue <P> que;for(int i = 0; i < 9; i++)   // 将所有位置都初始化为INFfor(int j = 0; j < 9; j++){d[i][j] = INF;}que.push(P(sx,sy));  // 将起点位置加入队列，并把这一点的距离设置为0d[sx][sy] = 0;while(que.size())    // 不断的循环队列，直到队列为空{P p = que.front();  // 从队列取出最前端的元素que.pop();if(p.first == gx && p.second == gy)break;for(int i = 0; i < 4; i++){int nx = p.first + dx[i], ny = p.second + dy[i];  // 移动之后的位置记为(nx,ny)if(0<=nx&&nx<9&&0<=ny&&ny<9&&maze[nx][ny]!=1&&d[nx][ny]==INF)  // 判断是否可以移动和访问过{que.push(P(nx,ny));  // 如果可以移动 则加入队列，并且到该位置的距离确定为到p的距离+1d[nx][ny] = d[p.first][p.second] + 1;}}}return d[gx][gy];
}
void solve(void)
{int res = BFS();cout<<res<<endl;
}
int main(void)
{int t;cin>>t;while(t--){cin>>sx>>sy>>gx>>gy;solve();}return 0;
}