A Knight's Journey

题意：给你一张地图，然后有一个骑士，骑士可以从地图的任意一个方格开始，作为起点，问你该骑士能否走遍整张题图。
题解：首先想到就是DFS，但是要对每个点进行一次DFS，时间复杂度估计hold不住，后来一想，有些点，不必搜索。因为已经收过，所以可以采取记忆化搜索。
但是这一题的难点不是这里，在于所谓的字典序输出，一开始不知道这里的字典序是指什么。后来才知道，就是找字母小的，字母相同就找数字小的，这样一来搜索到额顺序就确定了。

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
int map1[68][68];
int map2[68][68];
int n,m;
int xx[1602];
int yy[1602];
int num;
void DFS(int x,int y){
    xx[++num]=x;
    yy[num]=y;
    map2[x][y]=1;
  int dir[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};
    for(int i=0;i<8;i++){
        if(x+dir[i][0]<=n&&x+dir[i][0]>=1&&y+dir[i][1]<=m&&y+dir[i][1]>=1){
            if(!map2[x+dir[i][0]][y+dir[i][1]]){
                DFS(x+dir[i][0],y+dir[i][1]);
            }
        }

    }
    if(num==n*m)return;
    num--;//注意这里，如果没有当前没有找到全部的点并且有无路可走，
    map2[x][y]=0;//那么必须回溯，之前所记录的路中的点必须删除，而且该点应该被改为没有被访问过
}
int main(){
    int t;
    scanf("%d",&t);
    int ttt=1;
    while(t--){
        scanf("%d%d",&n,&m);
        memset(map1,0,sizeof(map1));
        for(int j=1;j<=m;j++){
            for(int i=1;i<=n;i++){
                if(!map1[i][j]){
                    map1[i][j]=1;
                    memset(map2,0,sizeof(map2));
                    num=0;
                    DFS(i,j);
                    if(num==n*m)
                        break;
                     for(int i=1;i<=n;i++)
                     for(int j=1;j<=m;j++){
                      if(map2[i][j])
                        map1[i][j]=map2[i][j];//统计之前已经找过的点
                        }
                }
            }
             if(num==n*m)
                     break;
        }
        printf("Scenario #%d:
",ttt++);
        if(num==n*m){
            for(int i=1;i<=n*m;i++){
               printf("%c%d",'A'+yy[i]-1,xx[i]);//注意这里的输出，把整型转化成A,B等字符
            }
            }
            else
                printf("impossible");
                printf("

");

    }
}

View Code