路径计数

问题描述
从一个 5 x 5 的方格矩阵的左上角出发，沿着方格的边走，满足以下条件的路线有多少种？

总长度不超过 12；
最后回到左上角；
路线不自交；
不走出 5 x 5 的方格矩阵范围之外。
如下图所示，ABC 是三种合法的路线。注意 B 和 C 由于方向不同，所以视为不同的路线。

在这里插入图片描述

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
答案：206
坑：五乘五的方格，走的却是边，所以走的路径的大小为6*6；从（0，0）出发要回到（0，0），（0，0）点无法被标记，所以会出现刚走出去一步就回来的情况，很明显不符合题意

//206
#include"bits/stdc++.h"
using namespace std;
int s=0;
int p[10][10];
int to[4][2]={1,0,-1,0,0,1,0,-1};
void ppp(int x,int y,int step)
{
	if(x==0&&y==0&&step>=4&&step<=12)//最少要绕一个格走回（0，0），此时路径数为4
	{
		s++;
		return;
	}
	for(int i=0;i<4;i++)
	{
		int xx,yy;
		xx=x+to[i][0];
		yy=y+to[i][1];
		if(p[xx][yy]==1)continue;
		if(xx>5||yy>5||xx<0||yy<0)continue;
		p[xx][yy]=1;
		ppp(xx,yy,step+1);
		p[xx][yy]=0;
	}
}
int main()
{
	ppp(0,0,0);
	cout<<s<<endl;
	return 0;
 }

相关文章