【经典算法问题】马的遍历【回溯】
【【经典算法问题】马的遍历【回溯】】
/*
马的遍历 回溯
在N*M的棋盘中的一点（x，y）开始遍历棋盘所有点
2014-4-8 20:10:48
*/
#include
#define max 1000struct 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;
}推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长