马走日 DFS c++ 算法解答weixin44378800的博客-

题目：
假设国际象棋棋盘有5*5共25个格子。设计一个程序，使棋子从初始位置（如图）开始跳马，需要将棋盘的格子全部都走一遍，每个格子只允许走一次。

问：总共有多少解。

思路：
DFS:
将起点作为搜索的起点，然后枚举马的八个走向，由于不是每个马都有八个走向，所以每走一步就要判断有没有越界，如果没有，就将当前点做为新的起点，然后继续递归走下一步，并把走过的地方标记为true，直到走到无路可走就结束递归，并且步数等于24时意味着遍历了所有格子（以（0，0）为起点），方案数加1。

ps: 总共有25个格子，sign[0][0] == true，只剩下24个格子，所以等 steps == 24 时相当于遍历结束。

#include<iostream> #include<algorithm> bool sign[5][5]; static int method = 0; int dx[] = {-2,-2,-1,-1,1,1,2,2}; int dy[] = {1,-1,2,-2,2,-2,1,-1}; bool check_route(int x, int y) { if(sign[x][y] == true) //note1 return false; if(x>=5 || x<0 || y<0 || y>=5) return false; return true; } void dfs(int steps, int x, int y) { if(steps == 24) {                 method++; return; } // Judge boundary  for(int i = 0; i <= 7; i++) { int m = x + dx[i]; int n = y + dy[i]; if( check_route(m ,n) ) {                         sign[m][n] = true; //mark: this grid has been covered dfs(steps+1, m, n);                         sign[m][n] = false; } } } int main() {         sign[0][0] = true; dfs(0,0,0);         std::cout <<"total methods:" << method << std::endl; } 

result：total methods –> 304

• 一个coding时遇到的小bug，希望大家不要像我一样粗心！源码中 note1的位置应该是 sign[x][y] == true;而不是sign[x][y] = true;噢！

以下是这个bug的结果：