- 图论
- 2016-08-31 17:19:26 @
// //简单迷宫问题:来自《算法竞赛入门经典》
/*输入: 迷宫大小的行n,列m
起点 stax,stay
终点 aix,aiy
输入迷宫:1为障碍,0可通过
输出:终点处的最短路径 dist[aix][aiy]
6 5
0 0
5 4
0 0 1 0 0
0 1 0 0 0
0 1 0 1 1
0 1 0 0 0
0 0 0 1 0
0 0 0 0 0 */
#include <stdio.h>
#define MAX 1000
int m,n;
int vis[MAX][MAX],fa[MAX][MAX],dist[MAX][MAX],maze[MAX][MAX];
int q[MAX*MAX];
int dx[4],dy[4];
void bfs(int x,int y)
{
int nx,ny;
int u,v,d,rear=0,front=0;
u=x*m+y;
q[rear++]=u; //入队
vis[x][y]=1;
fa[x][y]=u;
dist[x][y]=0;
while(front<rear)
{
v=q[front++];//出队
x=v/m;
y=v%m;
for(d=0;d<4;d++)
{
nx=x+dx[d];
ny=y+dy[d];
if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[nx][ny]&&vis[nx][ny]==0)
{
q[rear++]=nx*m+ny;
vis[nx][ny]=1;
fa[nx][ny]=v;
dist[nx][ny]=dist[x][y]+1;
}
}
}
}
int main()
{
int aix,aiy,stax,stay;
int i,j;
scanf("%d %d",&n,&m);
scanf("%d",&stax);
scanf("%d",&stay);
scanf("%d",&aix);
scanf("%d",&aiy);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%d",&maze[i][j]);
}
}
dx[0]=0,dy[0]=1;
dx[1]=1,dy[1]=0;
dx[2]=0,dy[2]=-1;
dx[3]=-1,dy[3]=0;
bfs(stax,stay);
printf("%d\n",dist[aix][aiy]);
return 0;
}
3 条评论
-
十三太保 LV 6 @ 2016-08-31 21:02:40
C++看不懂、
-
2016-08-31 21:02:38@
C++看不懂、
-
2016-08-31 17:35:27@
不用了...刚刚找出了错误
- 1