POJ 2488 A Knight’s Journey 解题报告

一、问题描述

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

二、解题思路

使用回溯法进行深度优搜索。

从A1开始搜索，如果能找到一个路径则立即返回，如果从A1出发搜索所有的路径都不能找到一个路径则输出impossible。

注意几个问题：
       1、是8个可能的搜索方向的顺序问题。网友贴出来一个顺序是dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

2、不要忘了输出空行。

三、代码

 

#include<iostream>
using namespace std;
struct Position
{
    int row;
    int col;
};
int Curr;//遍历个数

int Sum;//方格总数

int Row,Col;//棋盘行数和列数

Position path[50];//保存路径

bool V[50][50];//是否已经遍历

int dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
bool DFS(int r,int c )
{
    path[Curr].row=r;
    path[Curr].col=c;
    Curr++;
    if(Curr>Sum)
        return true;
    int R,C;
    for(int i=0;i<8;++i)
    {
        R=r+dir[i][0];
        C=c+dir[i][1];
        if(R>=1 && R<=Col && C>=1 && C<=Row && (V[R][C]==false))
        {    
            V[r][c]=true;
            if(DFS(R,C))
                return true;
            V[R][C]=false;
            Curr--;
        }
    }
    return false;
}
int main()
{
    int n;
    int i;
    //cout<
    cin>>n;
    for(i=1;i<=n;++i)
    {
        cin>>Row>>Col;
        memset(V,0,sizeof(bool)*50*50);
        Sum=Row*Col;
        Curr=1;
        
        cout<<"Scenario #"<<i<<":"<<endl;
        if(DFS(1,1))
        {
            for(int j=1;j<=Sum;j++)
            {
                cout<<(char)(path[j].row+64)<<path[j].col;
            }
            cout<<endl;
        }
        else
            cout<<"impossible"<<endl;
        cout<<endl;
    }
    return 0;
}