題目鏈接：http://poj.org/problem?id=2488 這段時間我貌似在找回我高中的遺憾啊……做搜索。。。 閑扯完畢，喜聞樂見的騎士遍歷，已經見過很多次了，但是經常是沒有做就拉倒了，最近被虐的本著臭不要臉的精神，接著虐……分八個方向深搜，搜著搜著就出來了，一邊搜一邊把那個那個路徑記錄下來，最后打印出來就行了（我竟然還想用string偷懶，但是明顯不可行啊……sigh，真是沒智商了，深搜都不會了……）
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 int f[30][30], ans[30][2], n, m;
9 bool g;
10 const int dir[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
11 bool inMap(int x, int y)
12 {
13 return x >= 0 && x < m && y >= 0 && y < n;
14 }
15 void dfs(int x, int y, int k)
16 {
17 if (k == n * m)
18 {
19 for (int i = 0; i < k; i++)
20 printf("%c%d", ans[i][0] + 65, ans[i][1] + 1);
21 printf("\n");
22 g = 1;
23 return;
24 }
25 for (int i = 0; i < 8; i++)
26 {
27 int xx = x + dir[i][0];
28 int yy = y + dir[i][1];
29 if (inMap(xx, yy) && !f[xx][yy] && !g)
30 {
31 f[xx][yy] = 1;
32 ans[k][0] = xx; ans[k][1] = yy;
33 dfs(xx, yy, k + 1);
34 f[xx][yy] = 0;
35 }
36 }
37 }
38 int main()
39 {
40 int t;
41 while (~scanf("%d", &t))
42 {
43 for (int i = 1; i <= t; i++)
44 {
45 memset(f, 0, sizeof(f));
46 memset(ans, 0, sizeof(ans));
47 g = 0;
48 scanf("%d%d", &n, &m);
49 f[0][0] = 1;
50 ans[0][0] = ans[0][1] = 0;
51 printf("Scenario #%d:\n", i);
52 dfs(0, 0, 1);
53 if (!g) printf("impossible\n");
54 printf("\n");
55 }
56 }
57 return 0;
58 }
59
|