最少步数
时间限制：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）分别表示起点的行、列，终点的行、列。 - 输出
- 输出最少走几步。
- 样例输入
-
2
3 1 5 7
3 1 6 7 - 样例输出
-
12
11题解：dfs带回溯；找最小步数；还可以用广搜BFS，以及用优先队列优化；
- 代码：
-
#include<stdio.h>
#include<string.h>
#define MIN(x,y) x<y?x:y
const int MAXN=;
const int INF=<<;
int map[MAXN][MAXN]={
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,}
};
int disx[]={,-,,};
int disy[]={,,-,};
int a,b,c,d,min;
void dfs(int x,int y,int t){int nx,ny;
if(x==c&&y==d){
min=MIN(min,t);
return ;
}
for(int i=;i<;i++){
nx=x+disx[i];ny=y+disy[i];
if(t+<min&&!map[nx][ny]){
map[nx][ny]=;
dfs(nx,ny,t+);
map[nx][ny]=;
}
}
return ;
}
int main(){
int T;
/* for(int x=0;x<9;x++){
for(int y=0;y<9;y++)printf("%d ",map[x][y]);
puts("");
}*/
scanf("%d",&T);
while(T--){min=INF;
scanf("%d%d%d%d",&a,&b,&c,&d);
map[a][b]=;
dfs(a,b,);
map[a][b]=;
printf("%d\n",min);
}
return ;}广搜：
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
const int INF=0xfffffff;
int disx[]={,,-,};
int disy[]={,,,-};
struct Node{
int nx,ny,step;
};
queue<Node>dl;
Node a,b;
int x,y,ex,ey,T,mi;
int map[][];
void bfs(){
map[x][y]=;
a.nx=x;a.ny=y;a.step=;
dl.push(a);
while(!dl.empty()){
a=dl.front();
dl.pop();
map[a.nx][a.ny]=;
if(a.nx==ex&&a.ny==ey){
if(a.step<mi)mi=a.step;
map[ex][ey]=;
}
for(int i=;i<;i++){
b.nx=a.nx+disx[i];b.ny=a.ny+disy[i];b.step=a.step+;
if(!map[b.nx][b.ny]&&b.step<=mi&&b.nx>=&&b.ny>=&&a.nx<&&b.ny<)dl.push(b);
}
}
}
int main(){
scanf("%d",&T);
while(T--){int m[][]={
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,}
};
memcpy((int *)map,(int *)m,sizeof(m[][])*);
scanf("%d%d%d%d",&x,&y,&ex,&ey);
mi=INF;
bfs();
printf("%d\n",mi);
}
return ;
}#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
const int INF=0xfffffff;
int disx[]={,,-,};
int disy[]={,,,-};
struct Node{
int nx,ny,step;
friend bool operator < (Node a,Node b){
return a.step > b.step;
}
};
priority_queue<Node>dl;
Node a,b;
int x,y,ex,ey,T,mi;
int map[][];
void bfs(){
map[x][y]=;
a.nx=x;a.ny=y;a.step=;
dl.push(a);
while(!dl.empty()){
a=dl.top();
dl.pop();
map[a.nx][a.ny]=;
if(a.nx==ex&&a.ny==ey){
if(a.step<mi)mi=a.step;
map[ex][ey]=;
}
for(int i=;i<;i++){
b.nx=a.nx+disx[i];b.ny=a.ny+disy[i];b.step=a.step+;
if(!map[b.nx][b.ny]&&b.step<=mi&&b.nx>=&&b.ny>=&&a.nx<&&b.ny<)dl.push(b);
}
}
}
int main(){
scanf("%d",&T);
while(T--){int m[][]={
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,}
};
memcpy((int *)map,(int *)m,sizeof(m[][])*);
scanf("%d%d%d%d",&x,&y,&ex,&ey);
mi=INF;
bfs();
printf("%d\n",mi);
}
return ;
}