时间限制：3000 ms | 内存限制：65535 KB
难度：4
输入
第一行输入一个整数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思路：这道题很简单 可以用深搜也可以用宽搜
宽搜代码：
描述
这有一个迷宫，有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）。）
最开始想的是让步数单独拿出来不放到结构体中，写完之后发现那样步数不是最小的，因为它会将无法走到终点但是走过的步数也记录下来所以必须将步数放到结构体中，那样步数就不会加无用的了
#include <stdio.h> #include <queue> using namespace std; struct Data{ //每个坐标的信息 int row; int col; int step; }; int direction[4][2] ={0,-1,-1,0,0,1,1,0}; //宽搜的上下左右的4个方向 int bfs(Data start,Data end) { bool map[9][9]={ //1表示墙壁 0表示道路 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 }; queue <Data> q; q.push(start); //将起始坐标放入队列 map[start.row][start.col] = 1; //该坐标访问过了，不在访问 Data t; while (!q.empty()) { //宽搜的核心代码 start = q.front(); q.pop(); if (start.row == end.row && start.col == end.col) { //如果已到终点则返回步数 return start.step; } for (int i = 0; i < 4; i++) { t.row = start.row+direction[i][0]; t.col = start.col+direction[i][1]; if (!map[t.row][t.col]) { //若map未访问则加入队列 t.step = start.step+1; q.push(t); map[t.row][t.col]=1; //表示已经访问过了 } } } } int main() { int n; scanf("%d",&n); Data a,b; //a表示起始坐标， b表示结束坐标 while (n--) { scanf("%d%d%d%d",&a.row,&a.col,&b.row,&b.col); a.step = 0; //最开始是零步， printf("%d\n", bfs(a, b)); } return 0; }
这是深搜：
#include <stdio.h> #include <algorithm> int cnt; int end_x,end_y; bool 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 }; void dfs(int x,int y,int step) { if(x==end_x&&y==end_y) { cnt = std::min(cnt,step); return ; } map[x][y] = 1; if(!map[x-1][y]) { dfs(x-1,y,step+1); } if(!map[x][y+1]) { dfs(x,y+1,step+1); } if(!map[x+1][y]) { dfs(x+1,y,step+1); } if(!map[x][y-1]) { dfs(x,y-1,step+1); } map[x][y] = 0;//要记得还原 } int main() { int n; scanf("%d",&n); while(n--) { int x,y; cnt = 0x3f3f3f3f; scanf("%d%d%d%d",&x,&y,&end_x,&end_y); dfs(x,y,0); printf("%d\n",cnt); } return 0; }
