3025: 踩方格（dfs）

解题思路:
n不超过20，先写一个dfs爆搜。

因为是二维数组，所以把只能向上、左、右走改成了向下、左、右走，起始位置在（0,50），这样向下左右走不会超过边界。

先将起始位置标记为-1，表示不能返回。

以走三步为例，所有可能走过的位置如图所示：

参考代码:

#include <iostream>
using namespace std;

int dx[3]={1,0,0};//下 左 右
int dy[3]={0,-1,1};
int dp[107][107];
int n,z;
void dfs(int x1,int y1,int k) {
	if(k==n){//走了n步，计数+1 
		z++;
		return;
	}
	for(int i=0; i<3; i++) {//三个方向 
		int x=x1+dx[i],y=y1+dy[i];
		if(dp[x][y]!=-1) {//如果没有走过 
			dp[x][y]=-1;//标记为走过 
			dfs(x,y,k+1);//向下一方向搜索 
			dp[x][y]=1;//因为要回溯，所以重新标记为没有走过 
		}
	}
}

int main() {
	cin>>n;
	dp[0][50]=-1;//起始点标记为-1 
	dfs(0,50,0);
	cout<<z<<endl;
	//打印查看 
//	for(int i=0; i<5; i++) {
//		for(int j=45; j<55; j++)cout<<dp[i][j]<<" \n"[j==54];
//	}

	return 0;
}