自动搬运

查看原文

来自洛谷，原作者为

	iiiiiiiiiiiiiiiiiii ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ

搬运于2025-08-24 22:35:01，当前版本为作者最后更新于2021-12-25 10:51:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

这道题的大意是要从地图的 $(1, 1)$ 点起，走到 $(n, n)$ 点，要求不能走在草堆上，并且转弯不能超过 $k$ 次，求有多少种可行的方案。

很明显，这是一道搜索题。我们可以在 dfs 函数中定义四个参数：$x$，$y$，$t$，$way$ ，分别表示当前的行、当前的列、当前转弯次数和方向（$0$ 代表往右走，$1$ 代表往下走）。代码如下：

//省略缺省源
int T,n,k,a[100][100];
int dfs(int x,int y,int t,int way)
{
	int sum=0;
	if(t>k||a[x][y])//如果转弯次数超过k次，或者该点是个草堆
		return 0;
	if(x==n&&y==n)//如果到达终点，方案数加一
		return 1;
	if(x<n&&!a[x+1][y])
		sum+=dfs(x+1,y,way?t:t+1,1);//往右走
	if(y<n&&!a[x][y+1])
		sum+=dfs(x,y+1,way?t+1:t,0);//往下走
	return sum;
}
int main()
{
	T=read();
	while(T--)
	{
		n=read(),k=read();
		char chr;
		for(int i=1;i<=n;i++)//输入地图
		{
			for(int j=1;j<=n;j++)
			{
				chr=getchar();
				if(chr=='.')
					a[i][j]=0;
				else
					a[i][j]=1;
			}
			chr=getchar();
		}
		printf("%d\n",dfs(1,2,0,0)+dfs(2,1,0,1));
	}
	return 0;
}

额，这就 $90$ 分, TLE 了。

我们会发现：在 dfs 的求解过程中，有许多重复的子问题。

记忆化搜索能很好的解决这种问题：开一个四维数组，如果之前没有求解过该状态的，就把该状态的方案数记录下来。以后如果遇到同样的状态的话，就可以直接返回该状态的方案数了。这有点绕

并且，在开始的时候，我们要把整个记忆化数组初始化为 $-1$。代码如下：

//省略缺省源
int T,n,k,a[100][100],g[100][100][10][5];//记忆化数组
int dfs(int x,int y,int t,int way)
{
	int sum=0;
	if(t>k||a[x][y])
		return 0;
	if(g[x][y][t][way]!=-1)//如果该状态求解过
		return g[x][y][t][way];//直接返回该状态的方案数
	if(x==n&&y==n)
		return 1;
	if(x<n&&!a[x+1][y])
		sum+=dfs(x+1,y,way?t:t+1,1);
	if(y<n&&!a[x][y+1])
		sum+=dfs(x,y+1,way?t+1:t,0);
	g[x][y][t][way]=sum;//标记
	return sum;
}
//主函数见上