马走 “日”
给你一个8*8的棋盘，从一个起点开始，按日字形走（如果行移动两格，列移动1格，如果列移动两格，行移动1格），走满整个棋盘，每个点只能走一遍，输出一个可行路径
一、dfs输出所有路径
一开始以为如果能走满整个棋盘，那么从任意起点开始搜索都能搜出答案，结果是错的，只能从一个特定的入口开始才能走完整个期盘
然后因为没有确定起点和终点，要走完整个棋盘，很慢很慢，即使是6x6的棋盘，虽然能走满整个棋盘，但是也要很久
#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<list> #define ll long long using namespace std; int a[8][8]; int dir[8][2] = { {2,1},{-2,-1},{-2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2} }; struct node { int x; int y; }p[10000]; bool flag = false; int ans = 0; void dfs(int x, int y, int cnt) { if (cnt >= 36) { cout << "------------------------------" << endl; for (int i = 0; i < 36; i++) { cout << p[i].x << " " << p[i].y << endl; } ans++; flag = true; return; } for (int i = 0; i < 8; i++) { int dx = x + dir[i][0]; int dy = y + dir[i][1]; if (a[dx][dy] == 0 && dx >= 0 && dx < 6 && dy >= 0 && dy < 6) { a[dx][dy] = 1; p[cnt].x = dx; p[cnt].y = dy; dfs(dx, dy, cnt + 1); a[dx][dy] = 0; } } } int main() { for (int i = 0; i < 6; i++) { for (int j = 0; j < 6; j++) { memset(a, 0, sizeof(a)); a[i][j] = 1; p[0].x = i; p[0].y = j; dfs(i, j, 1); if (flag) break; } if (flag) break; } /*bool flag=dfs(0, 0, 1);*/ cout << flag << " ans=" << ans << endl; return 0; }