最少步数
时间限制：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
原题来自：http://acm.nyist.net/JudgeOnline/problem.php?pid=58
代码一：dfs
// dfs
#include <stdio.h>
int ans,sx,sy,ex,ey;
bool vis[][],map[][]={
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,
}; void dfs(int i,int j,int cnt)
{
if(i<||i>||j<||j>||vis[i][j]||map[i][j]||cnt>=ans)return;
if(i==ex&&j==ey)
{
ans=cnt;
return;
} vis[i][j]=; // 这个已经遍历了x` dfs(i,j-,cnt+);
dfs(i-,j,cnt+);
dfs(i,j+,cnt+);
dfs(i+,j,cnt+); vis[i][j]=;
} int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
ans=;
dfs(sx,sy,);
printf("%d\n",ans);
}
return ;
}
代码二：bfs
/*BFS*/
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; #define N 9 typedef struct
{
int x,y,cnt;
}Node; int dir[][] = {{-,},{,},{,},{,-}};
int sx,sy,ex,ey;
int mp[N][N] =
{
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,}
};
int vis[N][N];
int bfs()
{
queue<Node> Q;
Node tmp,p;
p.x = sx; p.y = sy;
p.cnt = ;
memset(vis,,sizeof(vis));
vis[sx][sy] = ;
Q.push(p);
while(!Q.empty())
{
p = Q.front();
Q.pop();
if (p.x == ex && p.y == ey)
return p.cnt; for(int di=;di<;di++)
{
tmp.x = p.x + dir[di][]; tmp.y = p.y + dir[di][];
tmp.cnt = p.cnt + ;
if(tmp.x>= && tmp.x<= && tmp.y>= && tmp.y<= &&!vis[tmp.x][tmp.y] && !mp[tmp.x][tmp.y] )
{
Q.push(tmp);
vis[tmp.x][tmp.y] = ;
}
}
}
return -;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
printf("%d\n",bfs());
}
return ;
}
马上21点。要下课了，晚点我用求最短路径的算法来写写看，不求ac，只求学习，用不同的方法来实现它。
求最短路径常用算法：
戴克斯特拉算法（Dijkstra algorithm）：该算法解决的是有向图中单个源点到其他顶点的最短路径问题。
弗洛伊德算法（Floyd algorithm）：该算法解决的是有向带权图中两顶点之间最短路径的问题。
A*搜索算法：A*搜索算法，俗称A星算法。这是一种在图平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。
SPFA算法：中国人发明的算法，该算法是求单源最短路径的一种算法，在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作。