ACM 3984 迷宫问题
迷宫问题Time Limit: 1000MS Memory Limit: 65536K
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)
Source
下面贴上本人写的代码，已通过。
[cpp]
#include<stdio.h>
#define MAXSIZE 100
typedef struct{
int a[MAXSIZE];
int length;
}Maze;
void initiStack(Maze *m){
m->length = -1;
}
/* 进栈操作
* 参数 Maze *m : 栈结构
* 参数date ：进栈的数据
* 返回值：成功返回0，否则返回-1
*/ www.zzzyk.com
int inputStack(Maze *m, int date){
if(m->length >= MAXSIZE){
return -1;
}
m->length ++;
m->a[m->length] = date;
return 0;
}
/* 出栈操作
* 参数 Maze *m : 栈结构
* 返回值：成功返回栈顶的数据，否则返回-1；
*/
int outputStack(Maze *m){
if(m->length <= 0){
return -1;
}
return m->a[(m->length)--]; // 拿到当前栈顶的数据
}
/* 寻找通路的函数
* 参数 Maze* m : 存储路径的栈结构
* 参数 date[i][j] : 迷宫的二维表示方式，i 为行数, j 为列数
* 函数返回值：找到通路返回1，否则返回0
*/
int outputMaze(Maze *m, int date[][5]){
int i = 5, j = 5;
int h = 0, k = 0;
int temp = 0;
while(m->length >= -1){
if(k+1 < 5 && date[h][k+1] == 0){ // 往东走，坐标推算出为：(h,k+1)
if((temp = inputStack(m, h*10+k)) == -1){
printf("迷宫太大，需要更大的数组...");
return -1;
}else{
date[h][k] = 2;
k = k+1;
}
}
else if(h+1 < 5 && date[h+1][k] == 0){ // 往南走，坐标推算出为：(h+1,k)
if((temp = inputStack(m, h*10+k)) == -1){
printf("迷宫太大，需要更大的数组...");
return -1;
}else{
date[h][k] = 2;
h = h+1;
}
}else if(h-1 >= 0 && date[h-1][k] == 0){ // 往北走，坐标推算出为：(h-1,k)
if((temp = inputStack(m, h*10+k)) == -1){
printf("迷宫太大，需要更大的数组...");
return -1;
}else{
date[h][k] = 2;
h = h-1;
}
}else if(k-1 >= 0 && date[h][k-1] == 0){ /* 往西走，依据坐标可以推算出是 (h,k-1)*/
if((temp = inputStack(m, h*10+k)) == -1){
printf("迷宫太大，需要更大的数组...");
return -1;
}else{
date[h][k] = 2; /* 将走过的路径设一个标志为 2*/
k = k-1;
}
}else{
date[h][k] = 2;
if((temp = outputStack(m)) == -1){ // 如果四个方向或者没路，或者不能走时，就后退一步
break;
}else{
h = temp / 10;
k = temp % 10;
}
}
if(h == (i-1) && k == (j-1)){ // 当到达终点时直接跳出函数
inputStack(m, h*10 + k);
return 0;
}
}
printf("此迷宫没有通路");
return -1;
}
main
补充：综合编程 , 其他综合 ,
