Ural1298 Knight 經典DFS

這個題目很想當時剛開始學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 > 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