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

Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

题目链接：http://poj.org/problem?id=2488

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 int dir[][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};
 6 bool flag[27][27];
 7 struct node
 8 {
 9     int x,y;
10 }dd[27];
11 
12 int p,q;
13 int maxSize;
14 bool mark;
15 void init()
16 {
17     memset(flag,false,sizeof(flag));
18     maxSize=p*q;
19     mark=false;
20 }
21 bool judge(int x,int y)
22 {
23     if(x<1 || x>p || y<1 || y>q || flag[x][y])
24     {
25         return false;
26     }
27     return true;
28 }
29 void dfs(int x,int y,int step)
30 {
31     if(step==maxSize)
32     {
33         int i;
34         for(i=0;i<step;i++)
35         {
36             printf("%c%d",'A'+dd[i].y-1,dd[i].x);
37         }
38         printf("\n");
39         mark=true;
40         return;
41     }
42     if(mark)
43     return;
44     int i;
45     for(i=0;i<8;i++)
46     {
47         int xx=x+dir[i][0];
48         int yy=y+dir[i][1];
49         if(!judge(xx,yy))
50         {
51             continue;
52         }
53         dd[step].x=xx;
54         dd[step].y=yy;
55         flag[xx][yy]=true;
56         dfs(xx,yy,step+1);
57         if(mark)
58         return;
59         dd[step].x=0;
60         dd[step].y=0;
61         flag[xx][yy]=false;
62     }
63 }
64 int main()
65 {
66     int t;
67     scanf("%d",&t);
68     int cnt=1;
69     while(t--)
70     {
71         scanf("%d%d",&p,&q);
72         init();
73         int i,j;
74         printf("Scenario #%d:\n",cnt++);
75         for(i=1;i<=p;i++)
76         {
77             for(j=1;j<=q;j++)
78             {
79                 flag[i][j]=true;
80                 dd[0].x=i;
81                 dd[0].y=j;
82                 dfs(i,j,1);
83                 flag[i][j]=false;
84                 dd[0].x=0;
85                 dd[0].y=0;
86                 if(mark)
87                 break;
88             }
89             if(mark)
90             break;
91         }
92         if(!mark)
93         {
94             printf("impossible\n");
95         }
96         printf("\n");
97     }
98     return 0;
99 }

View Code

此题简单DFS，不过，还是花了不少时间，题目要求输出的路径（在此为一个字符串）是字典序最小，因此，dir[][2]方向数组的顺序就必须严格要求，其他的没什么陷阱