http://acm.pku.edu.cn/JudgeOnline/problem?id=2488
這是一道深搜回溯的題目。我這個(gè)新手初次做深搜，瀏覽了無數(shù)大牛的解題報(bào)告，收獲很大。我原來總以為是要用棧來存儲(chǔ)結(jié)點(diǎn)，卻沒想到回溯如此簡單。
1 #include<stdio.h>
2 #include<stdlib.h>
3 int n;
4 int r,c;
5 int ok;
6 int visit[100][100];
7 int px[50],py[50];
8 int yy[8] = {-1,1,-2,2,-2,2,-1,1};//在這就把輸出字典順序確定了
9 int xx[8] = {-2,-2,-1,-1,1,1,2,2};
10
11 int isok(int x,int y)
12 {
13 return x >= 1 && x <= r && y >= 1 && y <= c;
14 }
15
16 void dfs(int x,int y,int length);
17 int main()
18 {
19 scanf("%d",&n);
20 for(int i =1;i <= n;i++){
21 scanf("%d%d",&c,&r);
22 visit[1][1] = 1;
23 ok = 0;
24 dfs(1,1,1);
25 printf("Scenario #%d:\n",i);
26 if(ok){
27 for(int j = 1;j <= r*c;j++){
28 printf("%c",px[j]+'A'-1);
29 printf("%d",py[j]);
30 }
31 }
32 else printf("impossible");
33 printf("\n\n");
34 }
35 system("pause");
36 return 0;
37
38 }
39 void dfs(int x,int y,int length)
40 {
41 px[length] = x;
42 py[length] = y;
43 if(length == r*c){
44 ok = 1;
45 return;
46 }
47 for(int i = 0;i < 8;i++){
48 int tx = x + xx[i];
49 int ty = y + yy[i];
50 if(isok(tx,ty) && !visit[tx][ty] && !ok){
51 visit[tx][ty] = 1;
52 dfs(tx,ty,length+1);
53 visit[tx][ty] = 0;//巧妙，也是必須的
54 }
55 }
56 }
57
code