問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2488思路:
十分熟悉的DFS
需要注意的一點(diǎn)是: 字典序，所以八個(gè)方向的搜索次序不是任意的，從左向右，從上到下，這里定義:
1 const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
2 const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};
另外，我覺得只有從任何一個(gè)點(diǎn)出發(fā)都沒法遍歷，才應(yīng)該輸出impossible
不過，看了網(wǎng)上的代碼，都只需要從左上角出發(fā)即可得出結(jié)論
代碼:
1 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
2 struct Item {
3 int x, y;
4 } path[MAX_LEN];
5 int visited[MAX_LEN][MAX_LEN];
6 int row, col, flag;
7 const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
8 const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};
9
10 void
11 dfs(int depth, int x, int y)
12 {
13 int i, tx, ty;
14 visited[x][y] = 1;
15 path[depth].x = x;
16 path[depth].y = y;
17 if(depth+1 == row*col) {
18 if(!flag) {
19 flag = 1;
20 for(i=0; i<row*col; i++)
21 printf("%c%d", 'A'+path[i].y, path[i].x+1);
22 printf("\n");
23 }
24 }
25 if(!flag) {
26 for(i=0; i<8; i++) {
27 tx = x + dx[i];
28 ty = y + dy[i];
29 if(is_valid(tx, ty) && !visited[tx][ty])
30 dfs(depth+1, tx, ty);
31 }
32 }
33 visited[x][y] = 0;
34 }
35
36 void
37 solve()
38 {
39 int i, j;
40 memset(visited, 0, sizeof(visited));
41 flag = 0;
42 for(i=0; i<row; i++)
43 for(j=0; j<col; j++)
44 if(!flag)
45 dfs(0, i, j);
46 if(!flag)
47 printf("impossible\n");
48 }