这题目是一道深搜的题目,我们写一个递归函数叫Ways(int i, int j ,int n),i j就是当前所处的坐标,我们设置一个visited数组,简称 V 。
对于这个数组,首先初始化为零,然后我们递归的边界条件就是走完输入的步数的时候,就返回一。
如果没走完,就对当前的visited数组,当前的位置标记为一,说明已经走过,我们继续向下递归的时候,就不能再走这一块了。
因为每次向下递归的时候都是三叉的嘛,这实际上像是一颗三叉树,当我们走完以此点为基点进行探索的路径之后,我们就让这点的标记为零,因为三叉树此时,递归其它叉的时候,相当于是新走了一条路,与之前的搜寻是无关联的,有关联只是它们的双亲结点。
也就相当于是,我们站在某一点,后面的分叉已经走完之后,我们便回溯到双亲结点,然后原来站的点标记就被清零了,然后我们在进行之后的搜索。
这就是这道递归的思路。
#include <iostream>
#include <cstring>
using namespace std;
int V[50][50];
int Ways(int i,int j,int n)
{
if (n==0)
return 1;
V[i][j]=1;
int num=0;
if (!V[i+1][j])
num+=Ways(i+1,j,n-1);
if (!V[i][j+1])
num+=Ways(i,j+1,n-1);
if (!V[i][j-1])
num+=Ways(i,j-1,n-1);
V[i][j]=0;
return num;
}
int main()
{
int N;
cin>>N;
memset(V,0,sizeof(V));
cout<<Ways(0,25,N)<<endl;
return 0;
}