问题输入
一组数据，输入数据第1行为两个正整数m和n，m表示迷宫高度，n表示迷宫宽度，m<100,n<100；第2行为两个整数，分表表示起点的行列位置；第3为两个整数，分别表示终点的行列位置；其后为m行数据，每行n个整数，表示迷宫对应位置的状态，0表示通路，1表示障碍。
问题输出
以三元组形式（见P105）输出从起点到终点搜索到的第一条通路，没有则输出no
输入样例
8 8
1 1
8 8
0 0 1 0 0 0 1 0
0 0 1 1 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 1 0 0 0 0 0 0
输出样例
(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),(4,1,2),(5,1,1),(5,2,1),(5,3,2),(6,3,1),(6,4,1),(6,5,2),(7,5,2),(8,5,1),(8,6,1),(8,7,1),(8,8,1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include<stdio.h>
#include<stdlib.h>
#define Maxsize 10000
int **map;
typedef struct{
int x;
int y;
int di;
}seat;
typedef struct{
seat *base;
seat *top;
int size;
}sqStack;
int InitStack(sqStack *S){
S->base=(seat *)malloc(sizeof(seat)*Maxsize);
if(!S->base) exit(0);
S->size=Maxsize;
S->top=S->base;
return 1;
}
int Push(sqStack *S,seat a){
*S->top++=a;
return 1;
}
int GetTop(sqStack *S,seat *a){
if(S->base==S->top) return 0;
else *a=*--S->top;
return 1;
}
void Map(int x,int y){
map=(int **)malloc(sizeof(int *)*x);
for(int i=0;i<x;i++){
map[i]=(int *)malloc(sizeof(int)*y);
}
for(int i=0;i<x;i++){
map[i][0]=1;
map[i][y-1]=1;
}
for(int j=0;j<y;j++){
map[0][j]=1;
map[x-1][j]=1;
}
for(int i=1;i<x-1;i++){
for(int j=1;j<y-1;j++){
scanf("%d",&map[i][j]);
}
}
}
int findPath(int x1,int y1,int x2,int y2){
sqStack q;
InitStack(&q);
seat a,b,c;
int d,m,n,f;
a.x=x1;
a.y=y1;
map[x1][y1]=-1;
a.di=0;
Push(&q,a);
while(q.top!=q.base){
if((q.top-1)->x==x2&&(q.top-1)->y==y2) break;
d=(q.top-1)->di;
f=0;
while(d<=4){
d++;
switch(d){
case 1: m=(q.top-1)->x; n=(q.top-1)->y+1; break;
case 2: m=(q.top-1)->x+1; n=(q.top-1)->y; break;
case 3: m=(q.top-1)->x; n=(q.top-1)->y-1; break;
case 4: m=(q.top-1)->x-1; n=(q.top-1)->y; break;
}
if(map[m][n]==0){
map[m][n]=-1;
(q.top-1)->di=d;
b.x=m;
b.y=n;
b.di=0;
Push(&q,b);
f=1;
break;
}
}
if(f==0){
GetTop(&q,&c);
map[c.x][c.y]=3;
}
}
if((q.top-1)->x==x2&&(q.top-1)->y==y2){
for(seat *i=q.base;i<(q.top-1);i++){
printf("(%d,%d,%d),",i->x,i->y,i->di);
}
printf("(%d,%d,%d)",(q.top-1)->x,(q.top-1)->y,1);
return 0;
}
else printf("no");
}
int main(){
int X,Y,ax,ay,bx,by;
scanf("%d %d %d %d %d %d",&X,&Y,&ax,&ay,&bx,&by);
Map(X+2,Y+2);
findPath(ax,ay,bx,by);
}
|