|
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
107
108
109
110
111 |
#include <stdio.h>#include <string.h>#include <queue>using
namespace std;typedef
struct{ int
x,y; int
step;}V;queue <V> q;char
map[100][100];int
vis[100][100];int
main(){ int
i,j,n,m,x,y,cnt,num; V begin,end,tag,tag1; num=1; while(1) { scanf("%d%d",&m,&n); gets(map[0]); if
(n==0 && m==0) break; for
(i=0;i<=n+2;i++) { for
(j=0;j<=m+2;j++) { map[i][j]=‘ ‘; } } for
(i=1;i<=n;i++) { gets(map[i]); for
(j=m;j>=0;j--) { map[i][j+1]=map[i][j]; } map[i][0]=‘ ‘; } cnt=1; printf("Board #%d:\n",num++); while(1) { memset(vis,0,sizeof(vis)); scanf("%d%d%d%d",&begin.y,&begin.x,&end.y,&end.x); if
(begin.x==0 && begin.y==0 && end.x==0 && end.y==0) break; while(!q.empty()) { q.pop(); } begin.step=0; q.push(begin); while(!q.empty()) { tag=q.front(); if
(tag.x==end.x && tag.y==end.y) break; q.pop(); if
(vis[tag.x][tag.y]==1) continue; if
(map[tag.x][tag.y]==‘X‘
&& (tag.x!=begin.x || tag.y!=begin.y)) continue; vis[tag.x][tag.y]=1; x=tag.x-1; while(x>=0) { tag1.x=x; tag1.y=tag.y; tag1.step=tag.step+1; q.push(tag1); if
(map[tag1.x][tag1.y]==‘X‘) break; x--; } x=tag.x+1; while(x<n+2) { tag1.x=x; tag1.y=tag.y; tag1.step=tag.step+1; q.push(tag1); if
(map[tag1.x][tag1.y]==‘X‘) break; x++; } y=tag.y-1; while(y>=0) { tag1.x=tag.x; tag1.y=y; tag1.step=tag.step+1; q.push(tag1); if
(map[tag1.x][tag1.y]==‘X‘) break; y--; } y=tag.y+1; while(y<m+2) { tag1.x=tag.x; tag1.y=y; tag1.step=tag.step+1; q.push(tag1); if
(map[tag1.x][tag1.y]==‘X‘) break; y++; } } if
(!q.empty()) printf("Pair %d: %d segments.\n",cnt++,tag.step); else
printf("Pair %d: impossible.\n",cnt++); } printf("\n"); } return
0;} |
The Game(HOJ1140)----BFS,布布扣,bubuko.com
原文：http://www.cnblogs.com/xzenith/p/3633529.html