当前位置：首页 > news >正文

poj2488 A Knight's Journey 简单DFS 注意搜索步骤

news 来源：原创 2024/5/18 16:59:44

　　这一题是比较简单的搜索题，但是题目要求走法是按照字典序的，这样要求搜索时注意顺序。

 1 ///2014.3.10
 2 ///poj2488
 3 
 4 //16MS
 5 
 6 /**
 7  *简单的DFS，但是题目有个坑人的地方，就是字典序
 8  *因为要求字典序，在搜索时要注意搜索步骤
 9  *在搜索步骤上浪费了两个小时啊！！！
10  */
11 
12 #include <iostream>
13 #include <cstdio>
14 using namespace std;
15 
16 int p,q;
17 int coordinate_x[30]; ///记录每一步的坐标
18 int coordinate_y[30];
19 bool findit;          ///标记有没有找到走法
20 bool step[30][30];    ///标记每一个位置有没有走过
21 
22 void dfs(int x,int y,int deep)
23 {
24     if( findit )
25         return;
26     if( deep==p*q ){
27         findit = true;
28         coordinate_x[deep] = x;
29         coordinate_y[deep] = y;
30         return;
31     }
32 
33     step[x][y] = true;
34     coordinate_x[deep] = x;
35     coordinate_y[deep] = y;
36     if( x-1>=1 && x-1<=p && y-2>=1 && y-2<=q && !step[x-1][y-2] ){
37         dfs(x-1,y-2,deep+1);
38         step[x-1][y-2] = false;
39     }
40     if( x+1>=1 && x+1<=p && y-2>=1 && y-2<=q && !step[x+1][y-2] ){
41         dfs(x+1,y-2,deep+1);
42         step[x+1][y-2] = false;
43     }
44     if( x-2>=1 && x-2<=p && y-1>=1 && y-1<=q && !step[x-2][y-1] ){
45         dfs(x-2,y-1,deep+1);
46         step[x-2][y-1] = false;
47     }
48     if( x+2>=1 && x+2<=p && y-1>=1 && y-1<=q && !step[x+2][y-1] ){
49         dfs(x+2,y-1,deep+1);
50         step[x+2][y-1] = false;
51     }
52     if( x-2>=1 && x-2<=p && y+1>=1 && y+1<=q && !step[x-2][y+1] ){
53         dfs(x-2,y+1,deep+1);
54         step[x-2][y+1] = false;
55     }
56     if( x+2>=1 && x+2<=p && y+1>=1 && y+1<=q && !step[x+2][y+1] ){
57         dfs(x+2,y+1,deep+1);
58         step[x+2][y+1] = false;
59     }
60     if( x-1>=1 && x-1<=p && y+2>=1 && y+2<=q && !step[x-1][y+2] ){
61         dfs(x-1,y+2,deep+1);
62         step[x-1][y+2] = false;
63     }
64     if( x+1>=1 && x+1<=p && y+2>=1 && y+2<=q && !step[x+1][y+2] ){
65         dfs(x+1,y+2,deep+1);
66         step[x+1][y+2] = false;
67     }
68 }
69 
70 int main()
71 {
72 //    freopen("in","r",stdin);
73 //    freopen("out","w",stdout);
74 
75     int n;
76     int cas = 1;
77     scanf("%d",&n);
78     while( n-- ){
79         for(int i=0 ; i<27 ; i++)
80             for(int j=0 ; j<27 ; j++)
81                 step[i][j] = false;
82         findit = false;
83         scanf("%d%d",&p,&q);
84         dfs(1,1,1);
85         if( findit ){
86             printf("Scenario #%d:\n",cas);
87             for(int i=1 ; i<=p*q ; i++)
88                 printf("%c%d",'A'+coordinate_y[i]-1,coordinate_x[i]);
89             printf("\n\n");
90         }
91         else
92             printf("Scenario #%d:\nimpossible\n\n",cas);
93         cas++;
94     }
95     return 0;
96 }

　　在discuss中看到一个打表的代码，我怎么没想到呢~贴下来供以后启发思维

 1 #include <iostream>
 2 using namespace std;
 3 
 4 
 5 int main()
 6 {
 7     freopen("in.txt","r",stdin);
 8     int i,n,p,q;
 9     cin>>n;
10     for(i=1;i<=n;i++)
11     {
12         cin>>p>>q;
13         cout<<"Scenario #"<<i<<":"<<endl;
14         if(p==1 &&q ==1)
15             cout<<"A1"<<endl;
16         else if(p==3 && q==4)
17             cout<<"A1C2A3B1D2B3C1A2C3D1B2D3"<<endl;
18         else if(p==3 && q==7)
19             cout<<"A1B3D2F1G3E2G1F3E1G2E3C2A3B1C3A2C1D3B2D1F2"<<endl;
20         else if(p==3 && q==8)
21             cout<<"A1B3C1A2C3D1B2D3E1G2E3C2A3B1D2F1H2F3G1E2G3H1F2H3"<<endl;
22         else if(p==4 && q==3)
23             cout<<"A1B3C1A2B4C2A3B1C3A4B2C4"<<endl;
24         else if(p==4 && q==5)
25             cout<<"A1B3C1A2B4D3E1C2D4E2C3A4B2D1E3C4A3B1D2E4"<<endl;
26         else if(p==4 && q==6)
27             cout<<"A1B3C1A2B4C2D4E2F4D3E1F3D2B1A3C4B2A4C3E4F2D1E3F1"<<endl;
28         else if(p==5 && q==4)
29             cout<<"A1B3A5C4D2B1A3B5D4C2B4A2C1D3C5A4B2D1C3D5"<<endl;
30         else if(p==5 && q==5)
31             cout<<"A1B3A5C4A3B1D2E4C5A4B2D1C3B5D4E2C1A2B4D5E3C2E1D3E5"<<endl;
32         else if(p==6 && q==4)
33             cout<<"A1B3A5C6D4B5D6C4D2B1A3C2B4A2C1D3B2D1C3D5B6A4C5A6"<<endl;
34         else if(p==7 && q==3)
35             cout<<"A1B3C1A2C3B1A3C2B4A6C7B5A7C6A5B7C5A4B2C4B6"<<endl;
36         else if(p==7 && q==4)
37             cout<<"A1B3A5B7D6B5A7C6D4C2A3B1D2C4B2A4B6D7C5A6C7D5B4D3C1A2C3D1"<<endl;
38         else if(p==8 && q==3)
39             cout<<"A1B3C1A2B4C2A3B1C3A4B2C4A5B7C5A6B8C6A7B5C7A8B6C8"<<endl;
40         else
41             cout<<"impossible"<<endl;
42         cout<<endl;
43     }
44     return 0;
45 
46 }