题解 P6757 【[BalticOI2013] Tracks in the Snow】

· · 题解

My Blog

题目链接

题目解析

啊咧，是一道卡时间卡空间的好题目（划掉

我们可以先找到最后那只小动物最多能走过的结点，就是和左上角相连的一整个四联通连通块。（以下所有连通块都是指四联通

然后发觉这个连通块就可以让所有的小动物随便走了，因为无论如何走，最后总会被最后一只小动物覆盖。

那么把和这个连通块相连的其它连通块相连，可以通过第一个连通块枢纽一下就可以相互到达的连通块之间可以由同一个小动物来走。

考场上刚开始想要用并查集来写，先dfs一次把所有连通块缩成一个点，然后再dfs连边，算这些点到左上角连通块代表的那个点的距离的最大值就是答案。

然而这样时间和空间都不够优秀（所以就自闭了，本来想拿个部分分结果我这个算法写错了不太调得出来就开始重新想。

我们发现这个过程其实是在不断扩展联通块的过程。

从最后一个小动物的足迹形成的连通块开始，往相邻的另外一种足迹扩展，表示第二只小动物，形成一个新的大连通块就是这两只小动物的足迹范围，然后同理再次扩展，直到把所有的点都合在一起，答案就是扩展次数+1（加上最开始的连通块

当时有点自暴自弃，没有想到这就是接近正解的想法呢。

于是就可以先dfs第一个连通块，相同的就继续搜，不同的就丢到队列里（这就是我们下一只小动物扩展的地方）。然后从队列里取结点开始搜，搜过的地方打上标记可以不用再搜，理论上是O(n^2)的时间复杂度。

然后你就可以得到90pts的好成绩（雾（事实上，我考试的时候编号写挂了，挂成了60pts，惨

因为我写的dfs，会占用栈空间导致本不富裕的空间限制雪上加霜。

所以可以写bfs来规避掉这一点。

另外贴一个听评讲时的另外一种理解思路：

当某只动物走过雪地后，左上角和右下角必定是这种动物的足迹，且这两点之间有一个这种足迹形成的连通块，不妨设是兔子(R)。

很明显，若只有R，那么只需要1只动物即可；如果存在F，那么至少也要2只动物。

考虑什么情况下会有更多只动物。

所有与起点相连通的R，全都可以最后一只兔子完成，而如果某个足迹R被F包围成圈而无法与起点连通，那么肯定需要提前有一只兔子先走到这里，再让一只狐狸覆盖掉周围的足迹，最后再让一只兔子走一遍，这样就需要3只动物了。

容易发现，这种情况还可能会嵌套，即R和F交替地形成圆圈包围住另一种足迹，每多一圈就需要多一只动物。

于是可以把问题转化为：相邻的同种足迹之间边权为0，异种足迹之间边权为1，求出起点到所有点的最短路径，最短路径的最大值+1即为最少需要的动物数量。

这种只有0/1边权的问题是一个比较经典的可以用双端队列来解决的问题，把边权为0的塞到前端，边权为1的塞到后端。当然，写两个队列分开放也可以，这个连通块扩展的过程一定是交替的。

（不知道为啥打小动物的时候全程想到调查土壤小动物的丰富度，虽然这是兔子和狐狸，生物杀我qwq

►Code View

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define N 4005
#define M 16000005
#define INF 0x3f3f3f3f
#define LL long long
int rd()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f*x;
}
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int n,m,ans;
char s[N][N];
bool vis[N][N];
queue<int>Q[2];
inline bool check(int i,int j)
{
    if(i<1||i>n||j<1||j>m||s[i][j]=='.'||vis[i][j]) return 0;
    return 1;
}
void bfs()
{
    int now;
    if(s[1][1]=='R') Q[0].push(1),now=0;
    else Q[1].push(1),now=1;
    while(!Q[now].empty())
    {
        while(!Q[now].empty())
        {
            int x=Q[now].front();Q[now].pop();
            int j=x%m,i=x/m+1;
            if(j==0) j=m,i--;
            if(vis[i][j]) continue;
            vis[i][j]=1;
            for(int k=0;k<4;k++)
            {
                int x=i+dx[k],y=j+dy[k];
                if(!check(x,y)) continue;
                if(s[x][y]==s[i][j]) Q[now].push((x-1)*m+y);
                else Q[now^1].push((x-1)*m+y);
            } 
        }
        now^=1;
        ans++;
        //这个队列清完了 扩展另外一种颜色 答案++ 
    }
}
int main()
{
    freopen("track.in","r",stdin);
    freopen("track.out","w",stdout);
    n=rd(),m=rd();
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    bfs();
    printf("%d\n",ans);
    return 0;
}

►Code View Ver.2 dfs MLE

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define N 4005
#define M 16000005
#define INF 0x3f3f3f3f
#define LL long long
int rd()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f*x;
}
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int n,m,tot;
char s[N][N];
bool id[N][N];
queue<pair<int,int> >Q;
inline bool check(int i,int j)
{
    if(i<1||i>n||j<1||j>m||s[i][j]=='.'||id[i][j]) return 0;
    return 1;
}
inline void dfs(int i,int j,int num)
{
    id[i][j]=1;
    for(register int k=0;k<4;k++)
    {
        int x=i+dx[k],y=j+dy[k];
        if(!check(x,y)) continue;
        if(s[x][y]==s[i][j])
        {
            id[x][y]=1;
            dfs(x,y,num);
        }
        else Q.push(make_pair((x-1)*m+y,num+1));
    }
}
int main()
{
    freopen("track.in","r",stdin);
    freopen("track.out","w",stdout);
    n=rd(),m=rd();
    for(register int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    dfs(1,1,1);
    int ans=1;
    while(!Q.empty())
    {
        pair<int,int> x=Q.front();Q.pop();
        int j=x.first%m,i=x.first/m+1;
        if(j==0) j=m,i--;//Cao 这里打掉了 惨挂30pts
        if(!id[i][j])
            dfs(i,j,x.second);
        ans=max(ans,x.second);
    }
    printf("%d\n",ans);
    return 0;
}
/*
5 8
FFR.....
.FRRR...
.FFFFF.. 
..RRRFFR 
.....FFF
*/
/*
把连通块从最开始的情况扩张
扩张多少次所有点在一个集合里
*/