HDU 2488 A Knight's Journey(DFS)

Stay in a box all day , The knight felt particularly bored , therefore , He decided to come and go, but he could only go Japanese , And the world is no bigger than 88 The chessboard of . Can you help the brave knight make a travel plan ? Please find a way for the knight to walk through the chessboard . A knight can start or end in any square

Input
Enter a positive integer in the first line n, Represents the number of data groups for each group of data , Contains two positive integers p and q(1 <= pq <= 26), It means a p*q The chessboard of . The position of each square is represented by two characters , The first one from A Start , Representative column , The second is from 1 Start , On behalf of the line

Output
The result of each set of data is first a row "Scenario #i:", i Is the data serial number , from 1 Start and output one line , It is the first path to the chessboard in the dictionary , Then there is an empty line path that should be a continuous sequence of the positions of the blocks taken in turn. If there is no such path , Output "impossible"

Sample Input3
1 1
2 3
4 3Sample OutputScenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

understand ： For this question It must be DFS To do the There are two points we should pay attention to ：

1. First of all, we should pay attention to the problem of backtracking Deep search is very similar to the preorder traversal of a tree Think in terms of trees It may have reached the leaf node on the left, and there are still elements that have not been searched It is not difficult to understand that we need to go back
2. For every time DFS Judgment conditions for execution Because it is possible that we have traversed all the elements We need to jump out of the stack like structure we have established before So in addition to the general conditions We need to add a little more In my code, I set a bool Type variables Use the value of this variable as a judgment condition

The general idea of realization ：
A structure array is used to store the subscripts of rows and columns Use one bool Type variable to determine whether all elements have been traversed Then there is the backtracking and judgment conditions mentioned above

Here is the answer to this question AC Code ：`

Log in and copy

      
      

       
       //AC
       
       

       
       #include<stdio.h>
       
       

       
       #include<string.h>
       
       

       
       int 
       
       dx[
       
       8] 
       
       = {
       
       -
       
       1, 
       
       1, 
       
       -
       
       2, 
       
       2, 
       
       -
       
       2, 
       
       2, 
       
       -
       
       1, 
       
       1};
       
       

       
       int 
       
       dy[
       
       8] 
       
       = {
       
       -
       
       2, 
       
       -
       
       2, 
       
       -
       
       1, 
       
       -
       
       1, 
       
       1, 
       
       1, 
       
       2, 
       
       2};
       
       

       
       int 
       
       a[
       
       15][
       
       15];
       
       

       
       int 
       
       sum,
       
       m,
       
       n,
       
       ans
       
       =
       
       1;
       
       //ans Step number  
       
       

       
       bool 
       
       judge;
       
       

       
       struct 
       
       code
       
       
{
       
       
 
       
       int 
       
       col; 
       
       // That's ok  
       
       
 
       
       int 
       
       row;  
       
       // Column  
       
       
} 
       
       tmp[
       
       70];
       
       

       
       void 
       
       dfs(
       
       int 
       
       x,
       
       int 
       
       y,
       
       int 
       
       ans)
       
       
{
       
       
 
       
       tmp[
       
       ans].
       
       row
       
       =
       
       x;
       
       
 
       
       tmp[
       
       ans].
       
       col
       
       =
       
       y;
       
       
 
       
       if(
       
       ans
       
       ==
       
       m
       
       *
       
       n)
       
       
 {
       
       
  
       
       judge
       
       =
       
       true;
       
       
  
       
       return;
       
       
 }
       
       
 
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       8;
       
       i
       
       ++)
       
       
 {
       
       
  
       
       int 
       
       nx
       
       =
       
       x
       
       +
       
       dx[
       
       i];
       
       
  
       
       int 
       
       ny
       
       =
       
       y
       
       +
       
       dy[
       
       i];
       
       
  
       
       if(
       
       nx
       
       >=
       
       1 
       
       && 
       
       nx
       
       <=
       
       m 
       
       && 
       
       ny
       
       >=
       
       1 
       
       && 
       
       ny
       
       <=
       
       n 
       
       && 
       
       a[
       
       nx][
       
       ny]
       
       ==
       
       0 
       
       && 
       
       !
       
       judge)
       
       
  {
       
       
   
       
       a[
       
       nx][
       
       ny]
       
       =
       
       1;
       
       
   
       
       dfs(
       
       nx,
       
       ny,
       
       ans
       
       +
       
       1);
       
       
   
       
       a[
       
       nx][
       
       ny]
       
       =
       
       0;            
       
       // A very clever method of backtracking  
       
       
  }         
       
       // Start backtracking when there is no way to go  
       
       
 }
       
       
} 
       
       

       
       int 
       
       main()
       
       
{
       
       
 
       
       int 
       
       i,
       
       j,
       
       k;
       
       
 
       
       scanf(
       
       "%d",
       
       &
       
       sum);
       
       
 
       
       for(
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       sum;
       
       i
       
       ++)
       
       
 {
       
       
  
       
       judge
       
       =
       
       0;          
       
       // The first time there is an error  
       
       
  
       
       memset(
       
       a,
       
       0,
       
       sizeof(
       
       a));
       
       
  
       
       scanf(
       
       "%d %d",
       
       &
       
       m,
       
       &
       
       n);
       
       
  
       
       a[
       
       1][
       
       1]
       
       =
       
       1; 
       
       
  
       
       dfs(
       
       1,
       
       1,
       
       1);                      
       
       // The number of steps here each loop is initialized  
       
       
  
       
       printf(
       
       "Scenario #%d:\n",
       
       i
       
       +
       
       1);
       
       
  
       
       if(
       
       judge)
       
       
  
       
       for(
       
       int 
       
       j
       
       =
       
       1;
       
       j
       
       <=
       
       m
       
       *
       
       n;
       
       j
       
       ++)
       
       
  
       
       printf(
       
       "%c%d",
       
       tmp[
       
       j].
       
       col
       
       +
       
       'A'
       
       -
       
       1,
       
       tmp[
       
       j].
       
       row);
       
       
  
       
       else
       
       
  
       
       printf(
       
       "impossible");
       
       
  
       
       printf(
       
       "\n");
       
       
  
       
       if(
       
       i
       
       !=
       
       sum
       
       -
       
       1)
       
       
  
       
       printf(
       
       "\n");
       
       
 }
       
       
 
       
       return 
       
       0;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.
       
       
38.
       
       
39.
       
       
40.
       
       
41.
       
       
42.
       
       
43.
       
       
44.
       
       
45.
       
       
46.
       
       
47.
       
       
48.
       
       
49.
       
       
50.
       
       
51.
       
       
52.
       
       
53.
       
       
54.
       
       
55.
       
       
56.
       
       
57.