题解：P6757 [BalticOI2013] Tracks in the Snow

· · 题解

P6757 Tracks in the Snow 题解

题意

有两种小动物从一个矩阵的左上角开始到处乱逛，到右下角结束，每一时刻仅有一只小动物在矩阵上，狐狸走过的地方被标记为 F，兔子走过的地方被标记为 R，无小动物经过的点为 .，标记可被覆盖，先给出最后的矩阵，问至少有几只小动物经过。

思路

由于脚印可以覆盖，那么下一只小动物经过的地方上一只使可以随便踩的，故考虑倒推。为了使经过的小动物最少，在倒推过程中每只小动物必须将可以踩的地方都踩完，所以可以理解为是一个不断扩散联通块的过程。

同样可以证明，两种小动物交替经过（即不会出现连续两次经过同样的动物）时，实现给出矩阵所需的小动物最少。

实现

在经过上述分析之后，想要实现并不难，只需不断洪水填充不断取反和扩张，直到填完所有 F 和 R 即可，假设需要填充 x 次才能结束，那么算法的复杂度为 O(nmx)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define chg(x) (x == 'R'? 'F' : 'R') //宏定义，便于在填充时进行取反 
char a[4010][4010];
int n, m;
int filled; //记录每次填充的面积
int now; //记录当前填充的面积
int ans; //结果，即需要填充的次数
void dfs(int x, int y, char tp) { //洪水填充
    if(a[x][y] != tp) return ;
    if(x == 0 || x == n + 1 || y == 0 || y == m + 1) return ; //判边界
    a[x][y] = chg(tp); //取反
    ++filled; //填充时记录一次
    dfs(x + 1, y, tp);
    dfs(x - 1, y, tp);
    dfs(x, y + 1, tp);
    dfs(x, y - 1, tp);
}
signed main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i] + 1;
    do {
        now = filled;
        filled = 0;
        dfs(1, 1, a[1][1]);
        ++ans;
    } while(filled > now); //验证是否与上一次重合，如果是，则跳出循环
    cout << ans - 1; //由于需要多花一次填充来判断是否结束，所以输出时应减一 
    return 0;
}

然而结果不尽人意，只有可怜的 55 分。

看到评测结果的 TLE 和 MLE 不难想到其实是因为大量得重复搜索导致的，由于本代码是不断洪水填充来达到扩张的，根本目的是扩张，那么原来搜过的地方就不用搜了。

How? 可在每次搜索时通过栈（或者队列，原理相似）来存储下次搜索的起点，再次搜索时就由这些位置开始（当然在栈中同属一个联通快的点只搜一次就行了，其他的点可以舍去）这样就可以大量地跳过搜过的区域了，复杂度 O(nm)。

由于计入下次搜的起点的时候约等于实在找联通快的边界，那么数组大小开到矩阵面积的一半（即 8\times10^6）即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define chg(x) (x == 'R'? 'F' : 'R') //宏定义，便于将足迹取反 
struct point {
    int x, y;
};
char a[4010][4010];
bool vis[4010][4010];
int n, m;
point nxt[80000010]; //以栈的形式记录当前下一次开始填充的位置
point now[80000010];           //记录当前开始填充的位置
int t; //充当nxt[]的栈顶指针
int l; //表示now[]的长度
char tp;
int ans; //结果，即需要填充的次数
void dfs(int x, int y) { //洪水填充
    if(a[x][y] == '.' || vis[x][y]) return ;
    if(a[x][y] == chg(tp)) {
        nxt[++t] = {x, y}; //存入下次开始填充的位置
        return ;
    }
    if(x == 0 || x == n + 1 || y == 0 || y == m + 1) return ;
    vis[x][y] = true; //标记
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
}
signed main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i] + 1; //读入（废话
    t = 1;
    nxt[t] = {1, 1};
    tp = a[1][1]; //记录开始填充时对应的符号
    do {
        if(t) {
            l = t;
            for(int i = 1; i <= l; i++)
                now[i] = nxt[i]; //刷新填充起点
            t = 0;
            for(int i = 1; i <= l; i++) {
                if(!vis[now[i].x][now[i].y])
                    dfs(now[i].x, now[i].y);
            }
            ++ans;
        } else break;
        tp = chg(tp); //取反
    } while(t); //验证是否能继续搜
    cout << ans;
    return 0;
}

可见评测结果绿了不少，但是区区 92 分我们是绝对不能满意的。由于数组开的全是静态，所以 MLE 的罪魁祸首只能是洪水填充的过程，怎么处理呢？由于当我们存入下次搜索时的数据结构的栈，那么这事我不禁想起了当年学深搜用的幼儿园写法：用栈来搜（当然如果存的时候用的是队列那么广搜也是可以的）。这样可以大大减少递归时消耗的内存，那么这里不多解释，代码里见！

#include<bits/stdc++.h>
#define I return
#define AK 0
#define IOI ;
using namespace std;
#define chg(x) (x == 'R'? 'F' : 'R') //宏定义，便于将足迹取反 
struct point { //定义结构体，便于入栈 
    int x, y;
};
char a[4010][4010]; //读入的矩阵
bool vis[4010][4010]; //用以标记搜过的位置（这应该不用过多解释吧）
int n, m; //矩阵长宽
point nxt[80000010]; //以栈的形式记录当前下一次开始填充的位置
point now[160000010]; //栈，用于DFS
int t; //充当nxt[]的栈顶指针
int l; //表示now[]的长度
int ans; //结果，即需要填充的次数
point tmp; //表示DFS过程中当前搜到的位置
void dfs(char tp) { //洪水填充
    while(l) {
        tmp = now[l--];
        if(a[tmp.x][tmp.y] == chg(tp)) {
            nxt[++t] = tmp; //存入下次开始填充的位置
            continue;
        }
        vis[tmp.x][tmp.y] = true; //标记
        if(a[tmp.x + 1][tmp.y] != '.' && !vis[tmp.x + 1][tmp.y] && tmp.x != n) //入栈
            now[++l] = {tmp.x + 1, tmp.y};
        if(a[tmp.x - 1][tmp.y] != '.' && !vis[tmp.x - 1][tmp.y] && tmp.x != 1)
            now[++l] = {tmp.x - 1, tmp.y};
        if(a[tmp.x][tmp.y + 1] != '.' && !vis[tmp.x][tmp.y + 1] && tmp.y != m)
            now[++l] = {tmp.x, tmp.y + 1};
        if(a[tmp.x][tmp.y - 1] != '.' && !vis[tmp.x][tmp.y - 1] && tmp.y != 1)
            now[++l] = {tmp.x, tmp.y - 1};
    }
}
signed main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i] + 1; //读入（废话
    t = 1;
    nxt[t] = {1, 1}; //将搜索的起点压栈
    int tp = a[nxt[t].x][nxt[t].y]; //记录开始填充时对应的符号
    do {
        if(t) {
            l = t;
            for(; t; --t)
                now[t] = nxt[t]; //刷新填充起点
            for(int i = 1; i <= l; i++) {
                if(!vis[now[i].x][now[i].y]) //排除已经搜过但仍在栈中的情况
                    dfs(tp);
            }
            ++ans;
        } else break;
        tp = chg(tp); //取反
    } while(t); //验证是否能继续搜
    cout << ans;
    I AK IOI; //完美收场
}

结果：\huge\textrm {完美无瑕}\

50 个点AC真的爽！

另外蒟蒻调代码调了三个多小时，题解写了也近一个小时，甚至最后的代码都是在回家路上的地铁上写的......可以......留个小小的赞吗= )。