求马跳棋盘踏满5*5的国际象棋棋盘有多少种解法？

2019-11-06 07:18:01

字体：大中小

来源：转载

供稿：网友

这里写图片描述

题目如图所示。

#include<iostream>#include<cstdio>#define D 8#define N 5using namespace std;int chessboard[N][N];int chessboard_copy[N][N];int step[N*N+1];int step_num=0, result=0, flag=1;static int dx[D]={-2, -1, 1, 2, 2, 1, -1, -2};static int dy[D]={1, 2, 2, 1, -1, -2, -2, -1};void show01(){ cout<<"按5*5棋盘格式输出："<<endl; int i, j; for(i=0; i<N; ++i) { for(j=0; j<N; ++j) PRintf("%-2d ", chessboard[i][j]); cout<<endl; } cout<<endl;}void show(){ cout<<"按题目要求输出："<<endl; int i; cout<<"{ "; for(i=1; i<=N*N; ++i) printf("[%d,%d] ", i, step[i]); cout<<" }"<<endl<<endl;}void horse(int x, int y){ if(x>=0 && x<N && y>=0 && y<N && chessboard[x][y]==0) { //为了按题目输出，step_num是第几步，chessboard_copy[x][y]是棋盘标号 step[++step_num] = chessboard_copy[x][y]; //标记棋盘被访问 chessboard[x][y] = step_num; if(step_num == N*N) { if(flag) { show01(); show(); } //题目要求只输出一个解 flag = 0; result++; } int i; for(i=0; i<D; ++i) { horse(x+dx[i], y+dy[i]); } //回溯 chessboard[x][y] = 0; --step_num; }}int main(){ int i, j; //初始化棋盘副本的编号 for(i=0; i<N; ++i) for(j=0; j<N; ++j) chessboard_copy[i][j] = i*N+j+1; horse(0, 0); cout<<"总共解的种数为："<<result<<endl; return 0;}

上一篇：[LeetCode]387. First Unique Character in a String

下一篇：maven+spring mvc环境搭建注解版（无web.xml，maven jetty插件运行）