Posted on 2008-04-27 18:15
superman 阅读(602)
评论(1) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1148 C++ 00:00.01 872K */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 struct rec { int x, y, cnt, dir; };
8 struct { int x, y; } dir[4] = { {-1, 0}, {+1, 0}, {0, -1}, {0, 1} };
9
10 int main()
11 {
12 int w, h, board = 0;
13 bool map[77][77];
14
15 while(cin >> h >> w)
16 {
17 if(w == 0 && h == 0)
18 break;
19
20 board++;
21 cout << "Board #" << board << ':' << endl;
22
23 memset(map, false, sizeof(map));
24
25 for(int i = 1; i <= w; i++)
26 for(int j = 1; j <= h; j++)
27 switch(cin.get())
28 {
29 case 'X' : map[i][j] = 1; break;
30 case ' ' : map[i][j] = 0; break;
31 default : j--;
32 }
33
34 int sx, sy, tx, ty, pair = 0;
35 while(cin >> sy >> sx >> ty >> tx)
36 {
37 if(sx == 0 && sy == 0 && tx == 0 && ty == 0)
38 break;
39
40 pair++;
41 cout << "Pair " << pair << ": ";
42
43 bool repeat[77][77][4] = {false};
44
45 rec start = { sx, sy , 0, -1};
46 queue <rec> q; q.push(start);
47
48 rec cur;
49 int min = INT_MAX;
50 while(q.empty() == false)
51 {
52 cur = q.front(); q.pop();
53
54 for(int i = 0; i < 4; i++)
55 {
56 int x = cur.x + dir[i].x;
57 int y = cur.y + dir[i].y;
58
59 if(x == tx && y == ty)
60 min <?= (cur.cnt + (cur.dir != i));
61
62 if(x >= 0 && x <= w + 1 && y >= 0 && y <= h + 1)
63 if(map[x][y] == false && repeat[cur.x][cur.y][i] == false)
64 {
65 repeat[cur.x][cur.y][i] = true;
66 rec tmp = {x, y, cur.cnt + (cur.dir != i), i};
67 q.push(tmp);
68 }
69 }
70 }
71
72 if(min != INT_MAX)
73 cout << min << " segments." << endl;
74 else
75 cout << "impossible." << endl;
76 }
77 cout << endl;
78 }
79
80 return 0;
81 }
82