这有一个迷宫，有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 <queue>
#include <stdio.h>
#include <string.h>
using namespace std;
int map[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 vis[9][9], dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
struct Node
{
int x, y;
int num;
};
queue<Node>q;
int x1,x2,y1,y2;
void bfs()
{
while(!q.empty())
{
Node temp, node;
node = q.front();
q.pop(); //赋值后抛去首元素
for(int i = 0; i < 4; i++)
{
temp.num = node.num + 1;
temp.x = node.x + dir[i][0];
temp.y = node.y + dir[i][1];
if(vis[temp.x][temp.y] || map[temp.x][temp.y] ) //推断当前节点是否被訪问过,是否有路
continue;
if(temp.x == x2 && temp.y == y2)
{
cout<<temp.num<<endl;
return ;
}
vis[temp.x][temp.y] = 1;
q.push(temp); //该节点没被訪问过且有路，插入队列
}
}
}
int main()
{
int n;
//freopen("d:\test.txt","r",stdin);
cin>>n;
while(n--)
{
while(!q.empty()) q.pop();
memset(vis, 0, sizeof(vis));
cin>>x1>>y1>>x2>>y2;
if(x1 == x2 && y1 == y2)
{
cout<<"0"<<endl;
continue ;
}
Node node;
node.x = x1;
node.y = y1;
node.num = 0;
q.push(node); //(x1,y1)入队
bfs();
}
//fclose(stdin);
return 0;
}