問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1475思路:
很復雜的一題，從discuss知道可以采用嵌套的BFS來做，不過始終不知道如何下手
通過這題，發現自己對于復雜問題的coding能力比較弱，不能很好的理清其中的邏輯關系，需要多多鍛煉
這題的關鍵是抓住box的每一次擴展，都對應地存在一個person的起始位置，兩者需要同時記錄
參考:
http://www.chhaya.me/?p=147代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 21
5 /* north, south, east, west */
6 const int dx[] = {-1, 1, 0, 0};
7 const int dy[] = {0, 0, 1, -1};
8 const char dir_box[] = "NSEW";
9 const char dir_psn[] = "nsew";
10 int r, c;
11 int px, py, bx, by, btx, bty;
12 char map[MAX_LEN][MAX_LEN];
13 struct EACH {
14 int x, y;
15 int id;
16 int pre;
17 int dir;
18 };
19 struct EACH cur_each, tmp_each, cur_psn, tmp_psn, box_queue[MAX_LEN*MAX_LEN], psn_queue[MAX_LEN*MAX_LEN];
20 struct {
21 int x, y;
22 }persons[MAX_LEN*MAX_LEN];
23 int visited_box[MAX_LEN][MAX_LEN];
24 int visited_psn[MAX_LEN][MAX_LEN];
25 int cnt[MAX_LEN*MAX_LEN];
26 char seq[MAX_LEN*MAX_LEN][MAX_LEN*MAX_LEN];
27
28 int
29 is_valid_box(struct EACH item, int dir)
30 {
31 int tmpx, tmpy;
32 if(item.x<0 || item.x>=r || item.y<0 || item.y>=c || map[item.x][item.y]=='#')
33 return 0;
34 /* see if there exists a position for person to push */
35 tmpx = item.x-2*dx[dir];
36 tmpy = item.y-2*dy[dir];
37 if(tmpx<0 || tmpx>=r || tmpy<0 || tmpy>=c || map[tmpx][tmpy]=='#')
38 return 0;
39 return 1;
40 }
41
42 int
43 is_valid_psn(int psnx, int psny, int boxx, int boxy)
44 {
45 if(psnx<0 || psnx>=r || psny<0 || psny>=c || map[psnx][psny]=='#')
46 return 0;
47 /* path of person can't cover the box */
48 if(psnx==boxx && psny==boxy)
49 return 0;
50 return 1;
51 }
52
53 int
54 psn_bfs(int startx, int starty, int endx, int endy, int dir, int index)
55 {
56 int i, head, tail;
57 struct EACH tmp;
58 memset(visited_psn, 0, sizeof(visited_psn));
59 head = -1;
60 tail = 0;
61 psn_queue[tail].x = startx;
62 psn_queue[tail].y = starty;
63 psn_queue[tail].pre = -1;
64 visited_psn[startx][starty] = 1;
65 while(head < tail) {
66 ++head;
67 cur_psn = psn_queue[head];
68 if(cur_psn.x==endx && cur_psn.y==endy) {
69 /* record */
70 /* here 'index' should plus 1, according to box_bfs */
71 persons[index+1].x = cur_psn.x + dx[dir];
72 persons[index+1].y = cur_psn.y + dy[dir];
73 cnt[index+1] = 0;
74 tmp = cur_psn;
75 while(tmp.pre != -1) {
76 seq[index+1][cnt[index+1]++] = dir_psn[tmp.dir];
77 tmp = psn_queue[tmp.pre];
78 }
79 return 1;
80 }
81 for(i=0; i<4; i++) {
82 tmp_psn.x = cur_psn.x + dx[i];
83 tmp_psn.y = cur_psn.y + dy[i];
84 if(is_valid_psn(tmp_psn.x, tmp_psn.y, endx+dx[dir], endy+dy[dir]) && !visited_psn[tmp_psn.x][tmp_psn.y]) {
85 ++tail;
86 tmp_psn.pre = head;
87 tmp_psn.dir = i;
88 psn_queue[tail] = tmp_psn;
89 visited_psn[tmp_psn.x][tmp_psn.y] = 1;
90 }
91 }
92 }
93 return 0;
94 }
95
96 void
97 output(struct EACH *end)
98 {
99 int i, index;
100 if(end->pre == -1)
101 return;
102 output(box_queue+(end->pre));
103 index = end->id;
104 for(i=cnt[index]-1; i>=0; i--)
105 printf("%c", seq[index][i]);
106 printf("%c", dir_box[end->dir]);
107 }
108
109 void
110 box_bfs()
111 {
112 int i, psn_rt, head, tail;
113 head = -1;
114 tail = 0;
115 memset(visited_box, 0, sizeof(visited_box));
116 box_queue[tail].x = bx;
117 box_queue[tail].y = by;
118 box_queue[tail].pre = -1;
119 box_queue[tail].id = tail;
120 visited_box[bx][by] = 1;
121 persons[tail].x = px;
122 persons[tail].y = py;
123 while(head < tail) {
124 ++head;
125 cur_each = box_queue[head];
126 if(cur_each.x==btx && cur_each.y==bty) {
127 /* output */
128 output(box_queue+head);
129 return;
130 }
131 for(i=0; i<4; i++) {
132 tmp_each.x = cur_each.x + dx[i];
133 tmp_each.y = cur_each.y + dy[i];
134 if(is_valid_box(tmp_each, i) && !visited_box[tmp_each.x][tmp_each.y]) {
135 /* bfs for person */
136 psn_rt = psn_bfs(persons[head].x, persons[head].y, tmp_each.x-2*dx[i], tmp_each.y-2*dy[i], i, tail);
137 if(psn_rt) {
138 ++tail;
139 tmp_each.dir = i;
140 tmp_each.pre = head;
141 tmp_each.id = tail;
142 box_queue[tail] = tmp_each;
143 visited_box[tmp_each.x][tmp_each.y] = 1;
144 }
145 }
146 }
147 }
148 printf("Impossible.");
149 }
150
151 int
152 main(int argc, char **argv)
153 {
154 int i, j, tests = 0;
155 while(scanf("%d %d", &r, &c) != EOF) {
156 if(r==0 && c==0)
157 break;
158 for(i=0; i<r; i++) {
159 scanf("%s", map[i]);
160 for(j=0; j<c; j++) {
161 if(map[i][j] == 'S') {
162 px = i;
163 py = j;
164 } else if(map[i][j] == 'B') {
165 bx = i;
166 by = j;
167 } else if(map[i][j] == 'T') {
168 btx = i;
169 bty = j;
170 }
171 }
172 }
173 printf("Maze #%d\n", ++tests);
174 /* bfs */
175 box_bfs();
176 printf("\n\n");
177 }
178 }