题目:
在5X5的棋盘上,给定一位置,输出马回到原点有多少种不同的方案。
注意:马走的每一步必须在棋盘上,走斜日,如下图:
![](https://img-blog.csdnimg.cn/20210816202922649.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6eTIwMDhzeng=,size_16,color_FFFFFF,t_70)
输入:给定一位置,x ,y,中间有一空格隔开。
输出:可以回到原点的方案总数
样例输入:1 1
样例输出:61424
思路:
用深搜,先把所有方向遍历一遍,用zx和zy两个数组存放x和y的增量,再建立一个flag标记数组,将走过的地方标记为0,最后如果回到原点了,就num++
这里还有一个细节:变量pi(名字随便取的)是来记录是否是初始状态,因为原本马的位置就是在起点的,如果不设置好的话只会输出1
上代码:
#include<iostream>
using namespace std;
int zx[9]={0,2,1,-1,-2,-1,-2,1,2},zy[9]={0,1,2,2,1,-2,-1,-2,-1};
int flag[10][10],yx,yy,pi,num;
void dfs(int x,int y)
{
if(x==yx && y==yy && pi>0)
{num++;return;}
pi++;
for(int i=1;i<=8;i++)
{
int xx=x+zx[i],yyy=y+zy[i];
if(xx>=1 && xx<=5 && yyy>=1 && yyy<=5 && flag[xx][yyy]==0)
{
flag[xx][yyy]=1;
dfs(xx,yyy);
flag[xx][yyy]=0;
}
}
}
int main()
{
cin>>yx>>yy;
dfs(yx,yy);
cout<<num;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)