最少步数
时间限制： 3000 ms | 内存限制：65535 KB
难度： 4
- 描述
-
这有一个迷宫，有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,10表示道路，1表示墙。
现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？
（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）
- 输入
- 第一行输入一个整数n（0<n<=100），表示有n组测试数据; 随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。 输出
- 输出最少走几步。 样例输入
-
23 1 5 73 1 6 7
样例输出 -
1211
来源 - 上传者
-
1 #include
2 #include 3 #include 4 #include 5 using namespace std; 6 //int map[9][9]; 7 int ac[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1}; 8 struct posi 9 {10 int x, y, step;11 } s, t;12 int bfs(posi s, posi t, int map[9][9])13 {14 map[s.x][s.y] = 1; //标记作用， 有判断，必有标记； 15 int i;16 queue q; //队列中只有一个不断更新的结构体变量； 17 s.step = 0;18 q.push(s);19 while(!q.empty())20 {21 posi n;22 s = q.front();23 q.pop();24 if(s.x == t.x&& s.y == t.y) //递归结束； 25 {26 return s.step;27 }28 for(i=0; i<4; i++)29 {30 n.x = s.x + ac[i][0];31 n.y = s.y + ac[i][1];32 /* if(map[n.x][n.y] == 0)33 {34 map[n.x][n.y] = 1;35 //n.step = s.step + 1;36 q.push(n);37 38 } */39 if(map[n.x][n.y]==0)40 {41 n.step=s.step+1;42 map[n.x][n.y]=1;43 q.push(n);44 }45 }46 }47 }48 int main()49 {50 int h;51 scanf("%d", &h);52 while(h--)53 {54 int map[9][9]={55 1,1,1,1,1,1,1,1,1,56 1,0,0,1,0,0,1,0,1,57 1,0,0,1,1,0,0,0,1,58 1,0,1,0,1,1,0,1,1,59 1,0,0,0,0,1,0,0,1,60 1,1,0,1,0,1,0,0,1,61 1,1,0,1,0,1,0,0,1,62 1,1,0,1,0,0,0,0,1,63 1,1,1,1,1,1,1,1,1,};64 scanf("%d %d %d %d", &s.x, &s.y, &t.x, &t.y);65 int need = bfs(s, t, map);66 printf("%d\n", need);67 }68 return 0; 69 }