dfs

深搜(dfs)就是一條路搜到底再回溯的過程，不像廣搜那樣一層一層地搜，一般用於找一條符合的路徑就ok了，而不用找到最短的路;

今天做了一題很典型的深搜的題目，雖然之前做過挺多的，但是都沒有怎麼總結，寫起來不夠快...

其實總結起來還是有一個大概的框架的：

poj 2488.A Knight's Journey

這題就是找到一條路徑能夠遍歷所有格子的，但是要輸出字典序最小的一個序列，想想廣搜的話，好像不能保存一條路徑，深搜則挺合理的~

這題還是想了很多：

我本來的想法是每個格子都需要作為起點搜一遍，這樣耗時會比較大，但是也可以一旦找到了，就跳出所有循環，這樣就可以保證不超時，

所以現在總結起來一直超時的原因可能就是找到後沒有跳出..還要注意找到後也要跳出深搜的遞歸，加個判斷就可以了，所以總結起來就是：

加個flag標誌是否已經找到一條路徑~

然後記錄路徑的方式就是加一個深度的參數cur，每次把點放到數組a[cur]，最後滿了就數組a[]就行了！！！

initial flag = 0;

dfs:

　　if find a path:

　　　　print();

　　　　flag = 1;

　　a[cur] = now_point;

　　for i = 1 to 8:

　　　　find next position pi;

　　　　if !vis && valid() && !flag

　　　　　　vis(pi) = 1;

　　　　　　dfs(pi);

　　　　　　vis(pi) = 0;

當然還有另一個問題，就是如何保證字典序最小呢？？？

我一開始用一個vector <point> v　先八個方向存起來，就是next position；然後根據字典序排序，從小到大開始深搜，但是之前錯了幾次，

也不知道是不是因為這個，但是我覺得還是挺合理的...

然後看了別人說是為了字典序，所以要保證走的順序，就是找next position的時候，要先找小的，再找大的，準確來說就是如下圖的順序：

最後的最後，我覺得很奇怪的就是只從A1開始搜索，就可以過這題，而不需要每一個格子都作為起點搜一邊，這是我覺得很奇怪的地方，

我覺得這樣應該是不對的，也許是跟測試數據有關？幷不懂...

最後上代碼：

 1 // poj 2488.A Knight's Journey
 2 // dfs + 字典序 
 3 // http://blog.csdn.net/lyy289065406/article/details/6647666
 4 // http://www.cnblogs.com/rainydays/archive/2011/05/22/2053574.html
 5 #include <iostream>
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <algorithm>
 9 #include <vector>
10 
11 using namespace std;
12 
13 const int N = 30;
14 
15 struct point {
16     int x;
17     int y;
18 }a[N];
19 
20 bool vis[N][N];
21 int n, m;
22 int move_x[] = {-1, 1, -2, 2, -2, 2, -1, 1};    //注意方向顺序 
23 int move_y[] = {-2, -2, -1,-1, 1, 1, 2, 2};
24 bool flag;
25 
26 void dfs(int x, int y, int cur)
27 {
28     if(cur == n * m - 1) 　　//從0開始就要減1
29     {
30         for(int i=0; i<cur; i++)
31             printf("%c%d", a[i].y - 1 + 'A', a[i].x);
32         printf("%c%d
", y - 1 + 'A', x);
33         flag = 1;
34     }
35     a[cur].x = x;    //记录路径 
36     a[cur].y = y;
37     for(int i=0; i<8; i++)
38     {
39         point temp;
40         temp.x = x + move_x[i];
41         temp.y = y + move_y[i];
42         if(!vis[temp.x][temp.y] && temp.x >=1 && temp.x <= n && temp.y >=1 && temp.y <=m && !flag)
43         {
44             vis[temp.x][temp.y] = 1;
45             dfs(temp.x, temp.y, cur + 1);
46             vis[temp.x][temp.y] = 0;
47         }
48     }
49 }
50 
51 int main()
52 {
53     int k=1;
54     int t;
55     scanf("%d", &t);
56     while(t--)
57     {
58         flag = 0;
59         memset(vis, 0, sizeof(vis));
60         scanf("%d%d", &n, &m);
61         printf("Scenario #%d:
", k++);
62         /*for(int i=1; i<=n; i++)        //暴搜 
63         {
64             for(int j=1; j<=m; j++)
65             {
66         
67                 vis[i][j] = 1;    //标记起点 
68                 dfs(i, j, 0);
69                 if(flag)
70                     break;
71                 vis[i][j] = 0;
72             }
73             if(flag)
74                 break;
75         }*/
76         vis[1][1] = 1;    //这样也能ac 
77         dfs(1, 1, 0);
78         if(!flag)
79             printf("impossible
");
80         printf("
");
81     }
82     return 0;
83 }