P6285题解，来了！

· · 题解

思路

无聊的模拟题（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;
    }
}

注意点

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