最少步数
时间限制：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 - 来源
- [苗栋栋]原创
- 上传者
- 苗栋栋
少考虑的情况:起点与终点是同一个点
#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
struct Node
{
int r,c;
int ct;
}node;
int a[][]={ {,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,} };
int vis[][];
Node f[]={ {,,},{,-,},{,,},{-,,}};
int br,bc,er,ec;
queue<Node> q;
int bfs()
{
while()
{
if(q.empty())
{
return ;
}
Node temp = q.front();
q.pop();
for(int i=;i<;i++)
{ if(vis[temp.r+f[i].r][temp.c+f[i].c]== && temp.r+f[i].r>= && temp.r+f[i].r<= &&temp.c+f[i].c>= && temp.c+f[i].c<= && a[temp.r+f[i].r][temp.c+f[i].c]==)
{
vis[temp.r+f[i].r][temp.c+f[i].c]=;
Node b;
b.r = temp.r+f[i].r;
b.c = temp.c+f[i].c;
b.ct = temp.ct+;
if(b.r == er && b.c == ec)
{
return b.ct;
}
//printf("%d %d %d %d %d\n",b.r,b.c,b.ct);
q.push(b);
} }
}
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
for(i=;i<;i++)
for(j=;j<;j++)
vis[i][j]=;
while(!q.empty())
q.pop();
//int br,bc,er,ec;
scanf("%d %d %d %d",&br,&bc,&er,&ec);
//printf("%d %d",er,ec);
Node temp;
temp.r = br;temp.c = bc;temp.ct=;
vis[br][bc]=;
q.push(temp);
printf("%d\n",bfs());
}
return ;
}