迷宫问题
Time limit : 1000 ms Memory limit : 65536 kB
Problem Description
定义一个二维数组:
int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, };
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径,格式如样例所示。
Sample Input
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
Sample Output
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
#include <stdio.h>
struct node{
int x[25], y[25];
}p, q;//用p来存每次行走的坐标
int min = 99999999, next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int a[15][15], vis[15][15];
void dfs(int x, int y, int step)
{
p.x[step] = x;
p.y[step] = y;
if (x == 4 && y == 4)
{
if (step < min)
{
q = p;
min = step;
}
return ;
}
for (int k = 0; k < 3; k++)
{
int tx = x + next[k][0];
int ty = y + next[k][1];
if (tx < 0 || tx > 4 || ty < 0 || ty > 4)
continue;
if (a[tx][ty] == 0 && vis[tx][ty] == 0)
{
vis[tx][ty] = 1;
dfs(tx, ty, step + 1);
vis[tx][ty] = 0;
}
}
return ;
}
int main()
{
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
scanf("%d", &a[i][j]);
}
vis[0][0] = 1;
dfs(0, 0, 0);
for (int i = 0; i <= min; i++)
printf("(%d, %d)\n", q.x[i], q.y[i]);
return 0;
}