自动搬运

查看原文

来自洛谷，原作者为

	CoronaQL 朝着末日前进！

搬运于2025-08-24 22:19:19，当前版本为作者最后更新于2021-03-28 19:46:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

无聊的模拟题（COCI的原题），打起来有点烦。

在这里使用dp的方法实现比较方便。

设dpi,jdp_{i,j}dpi,j​为Mirko当前是否可以到达所定义位置(i,j)(i,j)(i,j)。 转移方程如下（伪代码）

dpi,j=dpi,j−1∣dpi+1,j−1(i=1)dp_{i,j}=dp_{i,j-1}|dp_{i+1,j-1}(i=1)dpi,j​=dpi,j−1​∣dpi+1,j−1​(i=1)
dpi,j=dpi+1,j−1∣dpi−1,j−1(2≤i≤9)dp_{i,j}=dp_{i+1,j-1}|dp_{i-1,j-1}(2≤i≤9)dpi,j​=dpi+1,j−1​∣dpi−1,j−1​(2≤i≤9)
dpi,j=dpi,j−1∣dpi−1,j−1(i=10)dp_{i,j}=dp_{i,j-1}|dp_{i-1,j-1}(i=10)dpi,j​=dpi,j−1​∣dpi−1,j−1​(i=10)

输出方案按照题意模拟即可，这里不细聊。

复杂度:O(n2)O(n^2)O(n2)

上AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100000//宏定义
int n,cnt;
char mp[11][MAXN+5];
int dp[11][MAXN+5];
int vis[MAXN+5];
void print(int x,int y)
{
	if(x==10&&dp[x][y-1])print(x,y-1);
	else if(x==10&&dp[x-1][y-1])print(x-1,y-1);
	else if(x==1&&dp[x][y-1]){vis[y-1]=1;print(x,y-1);}
	else if(x==1&&dp[x+1][y-1]){vis[y-1]=1;print(x+1,y-1);}
	else if(dp[x-1][y-1])print(x-1,y-1);
	else if(dp[x+1][y-1]){vis[y-1]=1;print(x+1,y-1);}
	else return ;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=10;i++)
		scanf("%s",mp[i]+1);
	for(int i=1;i<=10;i++)
		for(int j=1;j<=n;j++)
		dp[i][j]=0;
	if(mp[10][1]!='X')dp[10][1]=1;
	for(int j=2;j<=n;j++)
		for(int i=1;i<=10;i++)
		if(mp[i][j]!='X')
		{
			if(i==1)dp[i][j]|=dp[i][j-1],dp[i][j]|=dp[i+1][j-1];
			else if(i==10)
			dp[i][j]|=dp[i][j-1],dp[i][j]|=dp[i-1][j-1];
			else dp[i][j]|=dp[i-1][j-1],dp[i][j]|=dp[i+1][j-1];
		}
	for(int i=1;i<=10;i++)
	if(dp[i][n]){print(i,n);break;}
	for(int i=1;i<=n;i++)
	{
		int p=i;
		while(vis[p])p++;if(vis[i])cnt++;i=p;}
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++)
	{
		int p=i;
		while(vis[p])p++;
		if(vis[i])printf("%d %d\n",i-1,p-i);
		i=p;
	}
}

注意点

在这里我没有打注释，是希望大家能够通过我的思路来自己理解，而不是对着注释傻傻的看一遍，或者是直接复制粘贴，为了维护洛谷社区秩序，勿抄题解！