2016 CCPC 东北四省赛 D.
一道好题.
现场写崩了.
赛后LSh跟我讲了一种离散化的做法, 没听懂.
题意
一个$R cdot C (R, Cle 10^9)$ 的矩形点阵上有 $n (n le 200) $ 个坏点, 其余都是好点.
求好点的4-连通块 (以下简称cell) 的个数和每块的大小.
做法
我的想法是:
找出一个坏点的8-连通块, 在框住这个块的(最小)矩形区域内, 搜索当前8-连通块以及整个矩形点阵的边界 (以下简称"fence") 包围的cell.
这个想法大体上没什么漏洞.
要注意的问题有
- fence 套 fence 的情况
- 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<n; i++){
if(_x==x[i] && _y == y[i]){
return vis[i]==id?0:-3;
}
}
// good nut
if(_x<x1 || _x > 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数组+全局变量
一个好点的连通块合法的条件:
- 不超出矩形框
- 至少能遇到一个当前fence上的坏点
我们用两个全局的bool值 (flag) 来表示这两个条件是否成立, 再用一个全局变量记录当前连通块的大小.
Implementation
#include <bits/stdc++.h>
using namespace std;
const int N=205;
int x[N], y[N];
int vis[N];
// vector<int> 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<n; j++){
if(!vis[j] && x[j]==nx && y[j]==ny){
dfs(j);
break; // ?
}
}
}
}
int dx[]{-1, 1, 0, 0}, dy[]{0, 0, 1, -1};
bool used[205][205];
bool f1, f2;
int cnt;
void dfs(int _x, int _y){
// on border
if(_x==0 || _x==r+1 || _y==0 || _y==c+1){
return;
}
// out of range
if(_x<x1 || _x > x2 || _y < Y1 || _y > y2){
f1=false;
return;
}
// bad nut
for(int i=0; i<n; i++){
if(_x==x[i] && _y == y[i]){
if(vis[i]==id)
f2=true;
return;
}
}
// good nut
if(used[_x-x1][_y-Y1]){
return;
}
// cout<<_x<<' '<<_y<<endl;
used[_x-x1][_y-Y1]=true;
++cnt;
for(int i=0; i<4; i++){
int nx=_x+dx[i], ny=_y+dy[i];
dfs(nx, ny);
}
}
vector<long long> 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<<cnt<<endl;
// if(f1) puts("f1");
// if(f2) puts("f2");
if(f1 && f2 && cnt>0){
tot-=cnt;
res.push_back(cnt);
}
}
}
void solve(int n){
res.clear();
for(int i=0; i<n; i++){
vis[i]=0;
}
tot=(long long)r*c-n;
id=0;
for(int i=0; i<n; i++){
if(!vis[i]){
x1=Y1=INT_MAX;
x2=y2=INT_MIN;
++id;
dfs(i);
clac();
}
}
if(tot>0) res.push_back(tot);
sort(res.begin(), res.end());
printf("%lu
", res.size());
for(size_t i=0; i<res.size(); i++){
if(i) putchar(' ');
printf("%lld", res[i]);
}
puts("");
}
int main(){
int T, cas=0;
for(cin>>T; T--; ){
printf("Case #%d:
", ++cas);
cin>>r>>c>>n;
for(int i=0; i<n; i++){
scanf("%d%d", x+i, y+i);
}
solve(n);
}
return 0;
}
另外一个更隐蔽的坑:
DFS 的三个边界情况 (点阵边界, 超出矩形框, 坏点) 的顺序.