POJ 2488 A Knight's Journey

我会带着你远行 2022-06-18 11:00 176阅读 0赞

A Knight's Journey

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;44642</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;15167</td> 
  </tr> 
 </tbody> 
</table>

Description

![2488_1.jpg][] **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

题意：n行m列的棋盘，马以 L 型走，问马可以全部的棋盘格都走过一遍吗？

//dfs代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    int p,q,step;
    bool f;
    const int maxn = 30;
    int vst[maxn][maxn];
    int dir[8][2] = {
       {-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
    struct node
    {
        int x;
        int y;
    }res[maxn];
    
    void dfs(int x,int y)
    {
        if(f)
            return ;
        ++step;
        vst[x][y] = 1;// 标记该节点被访问过  
        res[step].x = x;//每一步的坐标
        res[step].y = y;
        if(step == p*q&&f == false)//
        {
            f = true;
            for(int i=1;i<=step;i++)
            {
                char c = res[i].x - 1+'A';
                cout<<c<<res[i].y;
            }
            cout<<endl;
            cout<<endl;
            return;
        }
        for(int i=0;i<8;i++)//遍历
        {
            int ex = x + dir[i][0];
            int ey = y + dir[i][1];
            if(ex >= 1&&ex<=q&&ey>=1&&ey<=p&&!vst[ex][ey])
                {
                    dfs(ex,ey);
                    step++;
                }
        }
    }
    
    int main()
    {
        //ios::sync_with_stdio(false);
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            step = 0;
            memset(vst,0,sizeof(vst));
            cout<<"Scenario #"<<i<<":"<<endl;
            cin>>p>>q;
            f = false;
            dfs(1,1);
            if(!f)
            {
                cout<<"impossible"<<endl<<endl;
            }
        }
        return 0;
    }

[2488_1.jpg]: /images/20220618/5e4259de3632450ba1c8a1b97bc6bf33.png