2016 CCPC 东北四省赛 D.

一道好题.

现场写崩了.

赛后LSh跟我讲了一种离散化的做法, 没听懂.

题意

一个$R \cdot C (R, C\le 10^9)$ 的矩形点阵上有 $n  (n \le 200) $ 个坏点, 其余都是好点.

求好点的4-连通块 (以下简称cell) 的个数和每块的大小.

做法

我的想法是:

找出一个坏点的8-连通块, 在框住这个块的(最小)矩形区域内, 搜索当前8-连通块以及整个矩形点阵的边界 (以下简称"fence") 包围的cell.

这个想法大体上没什么漏洞.

要注意的问题有

1. fence 套 fence 的情况
2. dfs的各种边界情况的顺序 (我是用dfs搜索好点的4-连通块的)

对于fence 套 fence 的情况, 如果对两个fence不加区分 就会导致重复统计.

Solution: 对每个 (可能的) fence 上的坏点编号.

实现上的坑

这题的坑真多 (至少对蒟蒻我而言如此)

一开始核心代码是这样写的:

int dx[]{-1, 1, 0, 0}, dy[]{0, 0, 1, -1};bool used[205][205];int dfs(int _x, int _y){    if(_x==0 || _x==r+1 || _y==0 || _y==c+1){        return -2;    }    for(int i=0; i
    
      x2 || _y < Y1 || _y > y2){        return -1;    }    if(used[_x-x1][_y-Y1]){        return 0;    }    used[_x-x1][_y-Y1]=true;    int res=0;    bool flag=false;    for(int i=0; i<4; i++){        int nx=_x+dx[i], ny=_y+dy[i];        int tmp = dfs(nx, ny);        if(tmp == -1){            return -1;        }        else if(tmp>=0) flag=true;        else if(tmp>0) res+=tmp;    }    return flag?res+1:0;}
    

这个dfs的目的是搜索好点的4-连通块, 同时判断该连通块是否合法.

然而我这种用返回值判断合法性的dfs写法却隐藏着一个bug:

注意dfs中的这样一段代码:

for(int i=0; i<4; i++){    int nx=_x+dx[i], ny=_y+dy[i];    int tmp = dfs(nx, ny);    if(tmp == -1){        return -1;    }    else if(tmp>=0) flag=true;    else if(tmp>0) res+=tmp;}

其中的

if(tmp == -1){    return -1;}

当dfs到一个超出当前矩形框的点时, 就会返回-1.

这样的写法在某些情况下会让好点也成为fence的一部分, 从而无法搜出一个好点的4-连通块. (这一点还会详谈)

比较好的写法:

vis数组+全局变量

一个好点的连通块合法的条件:

1. 不超出矩形框
2. 至少能遇到一个当前fence上的坏点

我们用两个全局的bool值 (flag) 来表示这两个条件是否成立, 再用一个全局变量记录当前连通块的大小.

Implementation

#include 
    
     using namespace std;const int N=205;int x[N], y[N];int vis[N];// vector
     
       st;int r, c, n;int x1, x2, Y1, y2;int id;void dfs(int i){    // st.push_back(i);    vis[i]=id;    x1=min(x1, x[i]);    x2=max(x2, x[i]);    Y1=min(Y1, y[i]);    y2=max(y2, y[i]);    for(int dx=-1; dx<=1; dx++)        for(int dy=-1; dy<=1; dy++){            int nx=x[i]+dx, ny=y[i]+dy;            for(int j=0; j
      
        x2 || _y < Y1 || _y > y2){        f1=false;        return;    }    // bad nut    for(int i=0; i
       
         res;long long tot;void clac(){    for(int i=x1; i<=x2; i++)        for(int j=Y1; j<=y2; j++){            used[i-x1][j-Y1]=false;        }    for(int i=x1; i<=x2; i++)        for(int j=Y1; j<=y2; j++){            f1=true, f2=false;            cnt=0;            dfs(i, j);            // cout<
        
         <
         
          0){ tot-=cnt; res.push_back(cnt); } }}void solve(int n){ res.clear(); for(int i=0; i
          
           0) res.push_back(tot); sort(res.begin(), res.end()); printf("%lu\n", res.size()); for(size_t i=0; i
           
            >T; T--; ){ printf("Case #%d:\n", ++cas); cin>>r>>c>>n; for(int i=0; i
           
          
         
        
       
      
     
    

另外一个更隐蔽的坑:

DFS 的三个边界情况 (点阵边界, 超出矩形框, 坏点) 的顺序.