这个题目很想当时刚开始学BFS时所做的一道题目，我记得是POJ，的也是马走日
这题目就是给了你一个n * n的棋盘，从（0,0）点出发，马走日的方式，是否可以将棋盘走遍，而且每个格子只能走一次
那天先是写了bfs，但是记录方式开了个三维的，最后超时，没办法改为dfs，然后就是一直WA，或者RE实在不明白是为什么，补题已经隔了两天了，我实在没有好的办法啊，最后又敲了一次，发现过了！找 之前的代码 发现就是dir数组不一样，真奇葩，就是 走有八个方向，顺序不一样 会WA？神奇的题目
做法简单，直接DFS并标记 即可，用一个容器来记录路劲，，最后发现 走到步数为 n*n就算是完成了
int n;int dir[8][2]={2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1};bool vis[10][10];vector<pair<int ,int > > G;int mark;int tot;void init() {memset(vis,false,sizeof(vis));mark = 0;G.clear();}bool input() {while(cin>>n) {return false;}return true;}int dfs(int x,int y,int step) {if(step == n * n){mark = 1;return step;}for(int i=0;i<8;i++) {int dx = x + dir[i][0];int dy = y + dir[i][1];if(dx < 0 || dx >= n || dy < 0 || dy >= n)continue;if(vis[dx][dy])continue;G.push_back(make_pair(dx,dy));vis[dx][dy] = true;dfs(dx,dy,step + 1);if(mark)return G.size();G.pop_back();vis[dx][dy] = false;}return 0;}void cal() {G.push_back(make_pair(0,0));tot++;vis[0][0] = true;dfs(0,0,1);if(!mark){puts("IMPOSSIBLE");return ;}for(int i=0;i<G.size();i++)printf("%c%d\n",G[i].first + 'a',G[i].second + 1);}void output() {}int main() {while(true) {init();if(input())return 0;cal();output();}return 0;}
车到山前必有路，没路可以先开路，开路就得有乐观，
