description

森林里有一片长方形的草地，在清晨的大雪过后被一层厚厚的积雪所掩盖（下图左）。

住在森林里的兔子和狐狸，穿越草地，都会在雪地上留下他们的踪迹。他们总是从左上角进入，并从右下角离开草地。在这两者之间，他们可以来回走动，在雪地里玩，甚至在同一个地方多次留下踪迹。在任何时候，最多只有一只动物在草地上，且所有的动物都只进入草地一次。这些动物的运动踪迹可以被简单的利用横纵坐标来描述。它们不会斜着走，也不会跳越一个单元格。当新的动物进入单元格，旧的足迹都将被新的足迹所覆盖。

例如，第一个兔子从左上角到右下角越过草地（图中）。在那之后，一只狐狸越过，则他的运动踪迹将会覆盖兔子的踪迹（图右）。

你将在一段时间后，得到一张描述草地上每个单元格的状态的地图。请写一个程序，计算可能出现的动物数目的最小值N。

analysis

• 倒数第一条路径明显已经知道，假设为同一个动物所为

• 那么贴着该路径的第二种颜色的格子一定被当前覆盖

• 假设倒数第二条路径走遍了倒数第一条路径的全部格子，即为最优解

• 该路径贴着的不同颜色的格子也同理

• 于是两个队列循环\(bfs\)即可

• 我不懂这种时间复杂度可以保证的题卡常数有什么意义

code

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define MAXN 4005
#define ll long long
#define fo(i,a,b) for (ll i=a;i<=b;++i)
#define fd(i,a,b) for (ll i=a;i>=b;--i)

using namespace std;

ll a[MAXN][MAXN];
bool bz[MAXN][MAXN];
ll f[4][2];
ll n,m,color,tot,ans;

struct node
{
    ll x,y;
}tmp;
queue<node>q[2];

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int main()
{
    //freopen("T2.in","r",stdin);
    n=read(),m=read();
    fo(i,1,n)
    {
        fo(j,1,m)
        {
            bz[i][j]=1;
            char ch=getchar();
            if (ch=='F')a[i][j]=1;
            else if (ch=='R')a[i][j]=2;
        }
        scanf("\n");
    }
    bz[1][1]=0;
    f[0][0]=-1,f[0][1]=0,f[1][0]=1,f[1][1]=0;
    f[2][0]=0,f[2][1]=-1,f[3][0]=0,f[3][1]=1;
    tmp.x=tmp.y=1,q[0].push(tmp);
    ll las=0,noww=1;
    while (ans==0 || (ans>0 && !q[las].empty()))
    {
        ++ans,color=a[q[las].front().x][q[las].front().y];
        while (!q[las].empty())
        {
            node now=q[las].front();q[las].pop();
            fo(i,0,3)
            {
                ll x=now.x+f[i][0],y=now.y+f[i][1];
                tmp.x=x,tmp.y=y;
                if (1<=x && x<=n && 1<=y && y<=m && bz[x][y])
                {
                    if (a[x][y]==color)bz[x][y]=0,q[las].push(tmp);
                    else if (a[x][y] && bz[x][y])bz[x][y]=0,q[noww].push(tmp);
                }
            }
        }
        noww^=1,las^=1;
    }
    printf("%lld\n",ans);
    return 0;
}

【JZOJ3319】雪地踪迹

原文：https://www.cnblogs.com/horizonwd/p/11151369.html