Posted on 2008-06-15 18:44
superman 閱讀(356)
評論(0) 編輯 收藏 引用 所屬分類:
POJ
1 /* Accepted 280K 16MS G++ 1675B */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, cnt, N;
7 bool visited[26][26], found;
8
9
10 struct { int x, y; } dir[8] = {
11 {-2, -1}, {-2, +1}, {-1, -2}, {-1, +2},
12 {+1, -2}, {+1, +2}, {+2, -1}, {+2, +1}
13 };
14
15 struct {int x, y; } path[26];
16
17 inline bool inside(const int x, const int y)
18 {
19 if(x >= 0 && x < n && y >= 0 && y < m)
20 return true;
21 return false;
22 }
23
24 void search(int x, int y)
25 {
26 if(found)
27 return;
28
29 visited[x][y] = true;
30 path[cnt].x = x, path[cnt].y = y;
31
32 if(cnt == n * m - 1)
33 {
34 found = true;
35 return;
36 }
37
38 for(int i = 0; i < 8; i++)
39 {
40 int xx = x + dir[i].x;
41 int yy = y + dir[i].y;
42 if(inside(xx, yy) && visited[xx][yy] == false)
43 {
44 cnt++;
45 search(xx, yy);
46 cnt--;
47 }
48 }
49
50 visited[x][y] = false;
51 }
52
53 int main()
54 {
55 scanf("%d", &N);
56 for(int i = 1; i <= N; i++)
57 {
58 found = false;
59 memset(visited, false, sizeof(visited));
60
61 scanf("%d %d", &m, &n);
62
63 printf("Scenario #%d:\n", i);
64
65 search(0, 0);
66
67 if(found)
68 for(int i = 0; i < n * m; i++)
69 printf("%c%d", path[i].x + 'A', path[i].y + 1);
70 else
71 printf("impossible");
72
73 printf("\n");
74
75 if(i < N)
76 printf("\n");
77 }
78
79 return 0;
80 }
81