题解：P6757 [BalticOI2013] Tracks in the Snow

· · 题解

P6757 [BalticOI2013] Tracks in the Snow 题解

题目传送门

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

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

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

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

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

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

正文

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

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

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

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

然后你就可以得到 90 分的好成绩（雾

因为写 dfs 会占用栈空间导致本不富裕的空间限制雪上加霜，所以可以写 bfs 来规避掉这一点。

代码如下（好难写啊）

#include<bits/stdc++.h>
using namespace std;

#define N 4005
#define M 16000005
#define INF 0x3f3f3f3f
#define LL long long

const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int n,m,ans;
char s[N][N];
bool vis[N][N];
queue<int> Q[2];

int read();
void bfs();
inline bool check(int,int);

int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
      scanf("%s",s[i]+1);
    bfs();
    printf("%d\n",ans);
    return 0;
}

int read() // 快读
{
    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;
}

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)
              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++;
        // 这个队列清完了 扩展另外一种颜色 答案++ 
    }
    return ;
}

inline bool check(int i,int j)
{
    if(i<1 || i>n || j<1 || j>m || s[i][j]=='.' || vis[i][j])
      return false;
    return true;
}

看到这里的哥哥姐姐们给个点赞再走喵~