首页 > 代码库 > POJ2488A Knight's Journey(dfs+数学)

POJ2488A Knight's Journey(dfs+数学)

2024-11-12 06:59:01   203人阅读

A Knight‘s Journey
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 32422 Accepted: 11040

Description

技术分享Background 
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey 
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. 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
 传送门


题意：判断一个棋盘是否能满足骑士周游问题，若满足就按字典序输出周游的步骤。

思路：dfs+数学。

数学可以用到，也可以用不到，dfs就是按照字典序搜索，即跳马的每一步要按字典序跳，对nxt数组处理一下即可。

数学可以用来剪枝，也可以不剪，而且只需要从A1开始dfs即可，因为如果可以遍历每一个点，那么一定可以从A1出发遍历每个点，欧拉回路和哈密顿路径保证了这点的正确性可以自己补充一下数学知识。

#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
int row,col,flag,top,CNT;
bool book[30][30];
struct note
{
    int x;
    int y;
}s[900];
int step[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}}; //跳马步按字典序
void ini()
{
    flag=top=0; CNT++;
    memset(book,0,sizeof(book));
    scanf("%d%d",&col,&row);
}
void dfs(int x,int y,int cnt)
{
    cnt++,top++;
    s[top].x=x;
    s[top].y=y;
    book[x][y]=1;
    if(cnt==row*col) {flag=1;return ;}
    for(int i=0;i<8&&!flag;i++){
        if(x+step[i][0]<1||x+step[i][0]>row||y+step[i][1]<1||y+step[i][1]>col||book[x+step[i][0]][y+step[i][1]]) continue;
        else dfs(x+step[i][0],y+step[i][1],cnt);
    }
    book[x][y]=0;
    if(flag==0) top--;
}
void solve()
{       
    dfs(1,1,0);  //只需对A1开始dfs
    printf("Scenario #%d:\n",CNT);
    if(!flag) printf("impossible");
    if(flag) for(int i=1;i<=top;i++){
        printf("%c%d",'A'+s[i].x-1,s[i].y);
    }
    puts("");
}
int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        ini();
        solve();
        if(_) puts("");
    }
    return 0;
}




POJ2488A Knight's Journey(dfs+数学)


联系
我们