首页 > 代码库 > poj 2488 A Knight's Journey（dfs）
poj 2488 A Knight's Journey（dfs）
Description
Background
Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board,
but it is still rectangular.
Can you help this adventurous knight to make travel plans?
Problem
Find a path such that the knight visits every square once.
The knight can start and end on any square of the board.
Input
The input begins with a positive integer n in the first line.
The following lines contain n test cases.
Each test case consists of a single line with two positive integers p and q,
such that 1 <= p * q <= 26.
This represents a p * q chessboard,
where p describes how many different square numbers 1, . . . , p exist,
q describes how many different square letters exist.
These are the first q letters of the Latin alphabet: A, . . .
Output
The output for every scenario begins with a line containing "Scenario #i:",
where i is the number of the scenario starting at 1.
Then print a single line containing the lexicographically first path
that visits all squares of the chessboard with knight moves followed by an empty line.
The path should be given on a single line by concatenating the names
of the visited squares.
Each square name consists of a capital letter followed by a number.
If no such path exist,
you should output impossible on a single line.
Sample Input
3
1 1
2 3
4 3
Sample Output
Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
这题大意是说 在n*m的格子里按照给定的八种方式跳跃能不能走完所有格子 如果能 按照字典序输出（这是个大坑）
还要注意每组要有一个空行
直接按照顺序进行搜索 反正最多也只有到26
#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define ll __int64#define MAXN 1000#define INF 0x7ffffff#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;struct N{ int x,y;};N num[300];int n,m,ok;int map[30][30];int dir[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};void dfs(int i,int j,int rt){ if(i<=0||j<=0||map[i][j]==-1||map[i][j]==1||ok) return ; rt++; map[i][j]=1; num[rt].x=j;//行列的顺序也需要注意 num[rt].y=i; if(rt==n*m) { ok=1; for(int a=1;a<=n*m;a++) { printf("%c%d",‘A‘-1+num[a].x,num[a].y); } printf("\n"); return ; } for(int a=0;a<8;a++) { int x=i+dir[a][0]; int y=j+dir[a][1]; if(x>0&&y>0&&map[x][y]==0) { dfs(x,y,rt); map[x][y]=0;//要注意回溯 } }}int main(){ int t,i,j,cnt=1; cin>>t; while(t--) { ok=0; //printf("Scenario #%d:\n",cnt++); 这个输出的顺序竟然不能在输入之前 真是奇葩 不过也学到了点 scanf("%d%d",&n,&m); printf("Scenario #%d:\n",cnt++); mem(map,-1); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { for(int k=1;k<=n;k++) for(int l=1;l<=m;l++)//虽然四重循环 但是数据比较小 map[k][l]=0; dfs(i,j,0); if(ok) {goto loop;} } loop: if(!ok) { printf("impossible\n"); } printf("\n"); } return 0;}