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
|
#include <stdlib.h>
#include <string.h>
#define SIZE 100000
typedef struct { int x,y;} node;
typedef struct { node base[SIZE]; int front,rear;} queue;
queue Q;
void (node e)
{
Q.base[Q.rear].x = e.x;
Q.base[Q.rear].y = e.y;
Q.rear = (Q.rear+1)%SIZE;
}
node pop()
{
node e;
e.x = Q.base[Q.front].x;
e.y = Q.base[Q.front].y;
Q.front = (Q.front + 1)%SIZE;
return e;
}
const int INF = 999999;
char map[220][220];
int N,M;
int find[220][220];
int iPlus[4] = {-1,0,1,0};
int jPlus[4] = {0,-1,0,1};
void BFS(node start)
{
int k;
Q.rear = 0;
Q.front = 0;
push(start);
node next,pre;
find[start.x][start.y] = 0;
while ( Q.rear!=Q.front )
{
pre = pop();
for ( k = 0; k < 4; k++)
{
next.x = pre.x + iPlus[k];
next.y = pre.y + jPlus[k];
if ( next.x >= 1 && next.x <= N && next.y >= 1 && next.y <= M)
{
if ( map[next.x][next.y] != '#' )
{
if (map[next.x][next.y]!='x')
{
if(find[next.x][next.y] >= find[pre.x][pre.y]+1)
{
find[next.x][next.y] = find[pre.x][pre.y]+1;
push(next);
}
}
else
{
if (find[next.x][next.y] >= find[pre.x][pre.y]+2)
{
find[next.x][next.y] = find[pre.x][pre.y]+2;
push(next);
}
}
}
}
}
}
}
int main()
{
freopen("Sample Input.txt","r",stdin);
system("Color F0");
int i,j;char ch;
node s,e;
while ( scanf("%d%d",&N,&M)!=EOF)
{
getchar();
for ( i = 1; i <= N; i++)
{
for ( j = 1; j <= M; j++)
{
scanf("%c",&ch);
if ( ch=='r') { s.x = i; s.y = j;}
if ( ch=='a') { e.x = i; e.y = j;}
map[i][j] = ch;
}
getchar();
}
for ( i = 1; i <= N; i++)
{
for (j = 1; j <= M; j++)
{
find[i][j] = INF;
}
}
BFS(s);
if (find[e.x][e.y]<INF)
printf("%dn",find[e.x][e.y]);
else
printf("Poor ANGEL has to stay in the prison all his life.n");
}
getch();
return 0;
}
|
近期评论