【经典算法问题】马的遍历【回溯】

/*
	马的遍历 回溯
	在N*M的棋盘中的一点（x，y）开始遍历棋盘所有点
	2014-4-8 20:10:48
*/
#include <stdio.h>
#define max 1000

struct Node{
	int x, y;
}moveXY[8] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, 
			{2, -1}, {2, 1}, {-2, 1}, {-2, -1}};

bool hasAccess[max][max];
Node store[max];
int n, m, id;

bool checkBound(int x, int y){
	if(x < 1 || y < 1 || x > n || y > m) return 0;
	return 1;
}

void print(){
	for(int i = 1; i <= id; ++i){
		if(i % 4 == 0) printf("\n");
		printf("(%d, %d) ", store[i].x, store[i].y);
	}
	printf("\n\n");
}
			
void backTrack(Node k){
	if(id == n * m){
		print();
		return;
	}
	Node temp;
	for(int i = 0; i < 8; ++i){
		if(checkBound(k.x + moveXY[i].x, k.y + moveXY[i].y) &&
			!hasAccess[k.x + moveXY[i].x][k.y + moveXY[i].y]){
			hasAccess[k.x + moveXY[i].x][k.y + moveXY[i].y] = 1;
			temp.x = k.x + moveXY[i].x;
			temp.y = k.y + moveXY[i].y;
			store[++id] = temp;
			backTrack(temp);
			--id;
			hasAccess[k.x + moveXY[i].x][k.y + moveXY[i].y] = 0;
		}
	}
}

int main(){
	int x, y;
	scanf("%d%d", &n, &m);
	scanf("%d%d", &x, &y);
	Node temp;
	temp.x = x; temp.y = y;
	store[++id] = temp;
	hasAccess[x][y] = 1;
	backTrack(temp);
	return 0;
}

【经典算法问题】马的遍历【回溯】,布布扣,bubuko.com

【经典算法问题】马的遍历【回溯】

原文：http://blog.csdn.net/chang_mu/article/details/23206657