加载中...

POJ 2488 - A Knight's Journey


0x00 POJ 原题

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

Source

TUD Programming Contest 2005, Darmstadt, Germany

0x10 题目概述

给出一个国际棋盘的大小,判断马能否不重复的走过所有格,并记录下其中按字典序排列的第一种路径。

经典的“骑士游历”问题,DFS 水题一道

0x20 解题思路

难度不大,但要注意的地方有 3 点:

  • 国际象棋的棋盘,行为数字 p;列为字母 q
  • 网上有同学说 这道题最后一组数据后是有空行的会 PE…,我测试过,不会的,能 AC
  • 题目要求以”lexicographically”方式输出,也就是字典序…要以字典序输出路径,那么搜索的方向(我的程序是 path() 函数)就要以特殊的顺序排列了…这样只要每次从 dfs(A,1) 开始搜索,第一个成功遍历的路径一定是以字典序排列…

下图是搜索的次序,马的位置为当前位置,序号格为测试下一步的位置的测试先后顺序

按这个顺序测试,那么第一次成功周游的顺序就是字典序

0x30 AC 源码

//Memory Time 
//240K   32MS 

#include<iostream>
using namespace std;

typedef class
{
    public:
        int row;
        char col;
}location;

int p,q;  //chess size = p*q
          //数字是行p,字母是列q
bool chess['Z'+1][27];

int x,y;  //返回值
void path(int i,int j,int num)  //ij为骑士当前在棋盘的位置 
{                               //num为骑士即将要跳到的位置序号
    switch(num)
    {
         case 1: {x=i-1; y=j-2; break;}     //注意这个尝试跳的顺序不能错   
        case 2: {x=i+1; y=j-2; break;}     //因为题目要求是字典序lexicographically输出
        case 3: {x=i-2; y=j-1; break;}     //这个顺序错了,必定WA
        case 4: {x=i+2; y=j-1; break;}
        case 5: {x=i-2; y=j+1; break;}
        case 6: {x=i+2; y=j+1; break;}
        case 7: {x=i-1; y=j+2; break;}
        case 8: {x=i+1; y=j+2; break;}
    }
    return;
}

bool DFS(location* way,int i,int j,int step)
{
    chess[i][j]=true;
    way[step].row=i;
    way[step].col=j;
    if(step==way[0].row)
        return true;

    for(int k=1;k<=8;k++)   //骑士从当前位置尝试跳到其他位置
    {
        path(i,j,k);
        int ii=x,jj=y;
        if(!chess[ii][jj] && ii>=1 && ii<=p && jj>='A' && jj<='A'+q-1)
            if(DFS(way,ii,jj,step+1))
                return true;
    }

    chess[i][j]=false;  //能执行到这步,说明前面跳的8步都不符合要求
    return false;       //即当前位置是错误位置,擦除记录返回上一步
}

int main(void)
{
    int test;
    cin>>test;
    int t=1;
    while(t<=test)
    {
        /*Initial*/

        memset(chess,false,sizeof(chess));

        cin>>p>>q;
        if(p==1 && q==1)      //范围缩窄,不要也能AC
        {
            cout<<"Scenario #"<<t++<<':'<<endl;
            cout<<"A1"<<endl<<endl;
            continue;
        }
        if(p*q>26 || p>=9 || q>=9 || p<=2 || q<=2)        //范围缩窄,不要也能AC
        {
            cout<<"Scenario #"<<t++<<':'<<endl;
            cout<<"impossible"<<endl<<endl;
            continue;
        }

        location* way=new location[p*q+1];   //记录走过的位置坐标
        way[0].row=p*q;   //记录总步数(棋盘总格子数)

        /*DFS*/

        bool flag=false;
        for(int j='A';j<='A'+q-1;j++)
        {
            for(int i=1;i<=p;i++)
                if(DFS(way,i,j,1))
                {
                    cout<<"Scenario #"<<t++<<':'<<endl;

                    for(int k=1;k<=way[0].row;k++)
                        cout<<way[k].col<<way[k].row;
                    cout<<endl<<endl;
                    flag=true;
                    break;
                }
                if(flag)
                    break;
        }

        if(!flag)
        {
            cout<<"Scenario #"<<t++<<':'<<endl;
            cout<<"impossible"<<endl<<endl;
        }
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
赏
  目录