首页 > 代码库 > poj2488（A Knight's Journey）

poj2488（A Knight's Journey）

2024-07-15 12:53:50   218人阅读

题目地址：A Knight‘s Journey

 

题目大意：

    骑士按照日字形走，给你p*q的棋盘，问你骑士能否走遍棋盘的所有位置，输出骑士走的路线序列p（1.2....）q（A.B...）

按照字典序输出，如果不能输出 ‘impossible‘ .

 

解题思路：

   搜索。因为是遍历全图所有点，所以必然经过A1. 又因为按字典序，既然A1可以经过，所以必然可以从A1开始。

   注意： 1.按照字典序输出意思为（先安A.B.C...）排序输出。

            const int dirx[]={-1,1,-2,2,-2,2,-1,1};

            const int diry[]={-2,-2,-1,-1,1,1,2,2};

            2.每组数据后有换行。

 

代码：

  1 #include <algorithm>  2 #include <iostream>  3 #include <sstream>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cstdio>  7 #include <string>  8 #include <bitset>  9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 32 /***************************************/ 33 void openfile() 34 { 35     freopen("data.in","rb",stdin); 36     freopen("data.out","wb",stdout); 37 } 38 priority_queue<int> qi1; 39 priority_queue<int, vector<int>, greater<int> >qi2; 40 /**********************华丽丽的分割线,以上为模板部分*****************/ 41 const int dirx[]={-1,1,-2,2,-2,2,-1,1}; 42 const int diry[]={-2,-2,-1,-1,1,1,2,2}; 43 int vis[30][30]; 44 int p,q; 45 int ce; 46 struct Node 47 { 48     int x; 49     char y; 50 } node[30]; 51 int DFS(int x,int y,int cnt) 52 { 53     int xx,yy; 54     if (cnt-1==p*q) 55     { 56         ce=1; 57         return 0; 58     } 59     for(int i=0; i<8; i++) 60     { 61          xx=x+dirx[i]; 62          yy=y+diry[i]; 63         if (xx>0&&xx<=p&&yy>0&&yy<=q&&!vis[xx][yy]) 64         { 65             // cnt++; 66             vis[xx][yy]=1; 67             node[cnt].x=xx; 68             node[cnt].y=yy; 69             DFS(xx,yy,cnt+1); 70             vis[xx][yy]=0; 71         } 72         if (ce) 73             return 0; 74     } 75 } 76 int main() 77 { 78     int cas; 79     int cntt=1; 80     scanf("%d",&cas); 81     while(cas--) 82     { 83         scanf("%d%d",&p,&q); 84         memset(vis,0,sizeof(vis)); 85         memset(node,0,sizeof(node)); 86         int cnt=1; 87         ce=0; 88         node[cnt].x=1; 89         node[cnt].y=1; 90         vis[1][1]=1; 91         DFS(1,1,cnt+1); 92         printf("Scenario #%d:\n",cntt++); 93         if (ce) 94         { 95             for(int i=1; i<=p*q; i++) 96             { 97                 printf("%c%d",node[i].y+‘A‘-1,node[i].x); 98             } 99             printf("\n");100         }101         else102             printf("impossible\n");103         if (cas)104             printf("\n");105     }106     return 0;107 }
View Code

 


联系
我们