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("
");
}
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
",ans);
return 0;
}