Posted on 2008-04-07 10:58
superman 閱讀(446)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1103 C++ 00:00.08 1188K */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 struct Rec { int p1, p2, p3, cnt; };
8
9 int main()
10 {
11 int n, p1, p2, p3;
12 while((cin >> n) && n)
13 {
14 cin >> p1 >> p2 >> p3;
15
16 char m[51][51];
17 for(int i = 1; i <= n; i++)
18 for(int j = 1; j <= n; j++)
19 cin >> m[i][j];
20
21 Rec cur = {p1, p2, p3, 0};
22 queue <Rec> rec;
23 rec.push(cur);
24
25 bool isRepeat[51][51][51] = {false};
26 isRepeat[p1][p2][p3] = true;
27 bool find = false;
28
29 while(rec.empty() == false)
30 {
31 cur = rec.front(); rec.pop();
32
33 if(cur.p1 == cur.p2 && cur.p2 == cur.p3)
34 {
35 cout << cur.cnt << endl;
36 find = true;
37 break;
38 }
39
40 for(int i = 1; i <= n; i++)
41 if(cur.p1 != i && m[cur.p1][i] == m[cur.p2][cur.p3])
42 if(isRepeat[i][cur.p2][cur.p3] == false)
43 {
44 isRepeat[i][cur.p2][cur.p3] = true;
45 Rec tmp = {i, cur.p2, cur.p3, cur.cnt + 1};
46 rec.push(tmp);
47 }
48 for(int i = 1; i <= n; i++)
49 if(cur.p2 != i && m[cur.p2][i] == m[cur.p1][cur.p3])
50 if(isRepeat[cur.p1][i][cur.p3] == false)
51 {
52 isRepeat[cur.p1][i][cur.p3] == true;
53 Rec tmp = {cur.p1, i, cur.p3, cur.cnt + 1};
54 rec.push(tmp);
55 }
56 for(int i = 1; i <= n; i++)
57 if(cur.p3 != i && m[cur.p3][i] == m[cur.p1][cur.p2])
58 if(isRepeat[cur.p1][cur.p2][i] == false)
59 {
60 isRepeat[cur.p1][cur.p2][i] = true;
61 Rec tmp = {cur.p1, cur.p2, i, cur.cnt + 1};
62 rec.push(tmp);
63 }
64 }
65 if(find == false)
66 cout << "impossible" << endl;
67 }
68
69 return 0;
70 }
71