Posted on 2009-04-23 10:54
superman 閱讀(122)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 enum { N, E, S, W };
6
7 struct Point
8 {
9 int x, y;
10
11 const Point next(int dir)
12 {
13 Point nextP;
14 switch (dir)
15 {
16 case N : nextP.x = x - 1, nextP.y = y; break;
17 case E : nextP.x = x, nextP.y = y + 1; break;
18 case S : nextP.x = x + 1, nextP.y = y; break;
19 case W : nextP.x = x, nextP.y = y - 1; break;
20 }
21 return nextP;
22 }
23 bool operator == (const Point & p)
24 {
25 return x == p.x && y == p.y;
26 }
27 } ;
28
29 char map[10][10];
30
31 bool inside(const Point & p)
32 {
33 return p.x >= 0 && p.x < 10 && p.y >= 0 && p.y < 10;
34 }
35 bool couldReach(const Point & p)
36 {
37 return map[p.x][p.y] == '.';
38 }
39
40 int main()
41 {
42 freopen("ttwo.in", "r", stdin);
43 freopen("ttwo.out", "w", stdout);
44
45 Point cowStartP, JohnStartP;
46
47 for (int i = 0; i < 10; i++)
48 for (int j = 0; j < 10; j++)
49 {
50 cin >> map[i][j];
51
52 if (map[i][j] == 'C')
53 cowStartP.x = i, cowStartP.y = j, map[i][j] = '.';
54 if (map[i][j] == 'F')
55 JohnStartP.x = i, JohnStartP.y = j, map[i][j] = '.';
56 }
57
58 int curTime = 0;
59 int ReachTime[10][10][4][10][10][4];
60
61 memset(ReachTime, 255, sizeof(ReachTime));
62
63 Point cowCurP = cowStartP, JohnCurP = JohnStartP;
64 int cowCurDir = N, JohnCurDir = N;
65
66 while (true)
67 {
68 if (cowCurP == JohnCurP)
69 {
70 cout << curTime << endl;
71 return 0;
72 }
73
74 if (ReachTime[cowCurP.x][cowCurP.y][cowCurDir][JohnCurP.x][JohnCurP.y][JohnCurDir] != -1)
75 break;
76 else
77 ReachTime[cowCurP.x][cowCurP.y][cowCurDir][JohnCurP.x][JohnCurP.y][JohnCurDir] = curTime;
78
79 Point cowNextP, JohnNextP;
80
81 cowNextP = cowCurP.next(cowCurDir);
82 if (inside(cowNextP) && couldReach(cowNextP))
83 cowCurP = cowNextP;
84 else
85 cowCurDir = (cowCurDir + 1) % 4;
86
87 JohnNextP = JohnCurP.next(JohnCurDir);
88 if (inside(JohnNextP) && couldReach(JohnNextP))
89 JohnCurP = JohnNextP;
90 else
91 JohnCurDir = (JohnCurDir + 1) % 4;
92
93 curTime++;
94 }
95
96 cout << 0 << endl;
97
98 return 0;
99 }
100