POJ A Knight's Journey

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int MAXN=30;
 4 
 5 //国际象棋纵是数字，横是英文
 6 struct Node//用于最后字典序输出
 7 {
 8     int x,y;
 9 }node[MAXN];
10 
11 int t1[]={-1,1,-2,2,-2,2,-1,1};
12 int t2[]={-2,-2,-1,-1,1,1,2,2};
13 int vis[MAXN][MAXN];
14 
15 int q,p;
16 int flag;
17 
18 void DFS(int row,int col,int step)
19 {
20     if(flag) return ;
21     if(step==p*q) 
22     {
23         flag=1;
24         return ;//遍历结束
25     }
26     if(row<0 || row >=p || col<0 || col>=q) return;
27     if(vis[row][col]) return ;
28 
29     node[step].x=row;
30     node[step].y=col;
31     vis[row][col]=1;
32     for (int i=0;i<8;i++)//八个方向
33     {
34       if(!vis[row+t1[i]][col+t2[i]])
35           DFS(row+t1[i],col+t2[i],step+1);
36     } 
37     vis[row][col]=0;
38     
39 }
40 
41 int main()
42 {
43     int T;
44     int cas=1;
45     scanf("%d",&T);
46     while(T--)
47     {
48         memset(vis,0,sizeof(vis));
49         flag=0;
50         scanf("%d%d",&p,&q);
51         DFS(0,0,0);
52         printf("Scenario #%d:\n",cas++);
53         if(!flag) printf("impossible\n");
54         else
55         {
56             for (int i=0;i<p*q;i++)
57             {
58                 printf("%c%d",node[i].y+'A',node[i].x+1);
59             }
60             printf("\n");
61         }
62         printf("\n");
63     }
64     return 0;
65 }

int row[]= {-1,1,-2,2,-2,2,-1,1};
int col[]= {-2,-2,-1,-1,1,1,2,2};

#include<stdio.h>
#include<string.h>
const int MAXN=40;
int vis[MAXN][MAXN];
int row[]= {-1,1,-2,2,-2,2,-1,1};
int col[]= {-2,-2,-1,-1,1,1,2,2};
struct Node
{
    int x,y;
} node[MAXN];
int flag;
int p,q;

void DFS(int i,int j,int cur)
{
    if(flag) return ;
    if(cur==p*q)//这里也是问题，老是无法确定边界
    {
        flag=1;
        node[cur].x=i;
        node[cur].y=j;
        return ;
    }
    node[cur].x=i;
    node[cur].y=j;
    for(int k=0; k<8; k++)
    {
        int row_vis=row[k]+i;
        int col_vis=col[k]+j;
        if(row_vis>=1 && row_vis<=p && col_vis>=1 && col_vis<=q && vis[row_vis][col_vis]==0)
        {
            vis[row_vis][col_vis]=1;
            DFS(row_vis,col_vis,cur+1);
            vis[row_vis][col_vis]=0;
        }
    }
}

int main()
{
    int i,j;
    int T;
    int cas=1;
    scanf("%d",&T);
    while(T--)
    {
        flag=0;
        memset(vis,0,sizeof(vis));
        scanf("%d%d",&p,&q);
        for(i=1; i<=p; i++)
        {
            for(j=1; j<=q; j++)
            {
                if(flag) break;
                vis[i][j]=1;
                DFS(i,j,1);
                vis[i][j]=0;
            }
            if(flag) break;
        }
        printf("Scenario #%d:\n",cas++);
        if(!flag) printf("impossible");
        else
        {
            for(i=1; i<=q*p; i++)
            {
                printf("%c%d",node[i].y+'A'-1,node[i].x);
            }
        }
        printf("\n\n");
    }
    return 0;
}