这有一个迷宫，有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<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<stack> #include<queue> #define inf 0x3f3f3f #define M 10 using namespace std; struct data{ int x,y; int step; }; int v[9][9]; 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 to[4][2]={0,1,0,-1,1,0,-1,0}; bool check(int x,int y) { return x>=0&&x<=8&&y>=0&&y<=8&&!map[x][y]&&!v[x][y]; } void bfs(data st,data ed) { memset(v,0,sizeof(v)); queue <data> Q; data now,next; st.step=0; Q.push(st); while(!Q.empty()) { now=Q.front(); Q.pop(); if(now.x==ed.x&&now.y==ed.y) { printf("%d\n",now.step); return ; } for(int i=0;i<4;i++) { next.x=now.x+to[i][0]; next.y=now.y+to[i][1]; if(check(next.x,next.y)){ next.step=now.step+1; v[next.x][next.y]=1; Q.push(next); } } } } int main() { int n; scanf("%d",&n); while(n--) { data st,ed; scanf("%d%d%d%d",&st.x,&st.y,&ed.x,&ed.y); bfs(st,ed); } return 0; }