poj 2488 A Knight's Journey dfs加路径打印

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

Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

这道题的关键是进行路径打印，并且路径打印的时候要求按照字母的非降序打印，这就要求我们在搜索的时候要注意搜索的方向。

这里每匹马有八个方向可以走，为了达到题目的要求应该先搜索左边的四个方向，然后再搜索右边的四个方向，在同一列的方向

应该先搜索上面的方向，然后再搜索下方的方向，所以八个方向是：{-1,-2,1,-2,-2,-1,2,-1,-2,1,2,1,-1,2,1,2}

在做这道题的时候我忘记了一点：就是他如果能够将棋盘走完，一定能够从第一个位置开始走完整个棋盘。

下面是我的代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

struct node
{
  int x,y;
};

int p,q;
int vis[28][28];
int cnt,n;
int dir[8][2]={-1,-2, 1,-2, -2,-1, 2,-1, -2,1, 2,1, -1,2, 1,2};//八个方向
struct node path[28];//记录路径

int judge(int x,int y)
{
  if(x>=0&&x<p&&y>=0&&y<q&&!vis[x][y])
    return 1;
  return 0;
}

int dfs(int x,int y,int step)
{
  int sx,sy,n;
  vis[x][y]=1;
  path[step].x=x;path[step].y=y;
  if(step==p*q-1)
    return step;
  for(int i=0;i<8;i++)
  {
    if(judge(x+dir[i][0],y+dir[i][1]))
    {
      sx=x+dir[i][0];sy=y+dir[i][1];
      vis[sx][sy]=1;
      n=dfs(sx,sy,step+1);
      vis[sx][sy]=0;
      if(n==p*q-1)
        return n;
    }
  }
return 0;
}

int main()
{
  int t;
  bool flag;
  scanf("%d",&t);
  for(int Case=1;Case<=t;Case++)
  {
    flag=0;
    scanf("%d%d",&p,&q);
    memset(vis,0,sizeof(vis));
    cnt=dfs(0,0,0);
    if(cnt==p*q-1)  flag=1;
    printf("Scenario #%d:/n",Case);
    if(!flag)
      printf("impossible/n/n");
    else
    { 
      for(int k=0;k<=cnt;k++)
         printf("%c%d",path[k].y+'A',path[k].x+1);
      printf("/n/n");
    } 
  }
  
  return 0;
}

原文链接：https://blog.csdn.net/zhenzi_1989/article/details/6428593