题意：
给一个n*m的矩阵作为地图，0为通路，1为阻碍。只能向上下左右四个方向走。每一年会在一个通路上长出一个阻碍，求第几年最上面一行与最下面一行会被隔开。
输入：
首行一个整数t，表示共有t组数据。
每组数据首行两个整数n, m，表示矩阵大小。
接下来输入矩阵。
接下来输入一个整数q，表示一共q年。
接下来q行，第i行为两个整数xi, yi，表示在第i年会在xi, yi长出一个阻碍。数据保证只会在通路上生成阻碍。
输出：
如果在第i年被隔开，则输出i。如果始终无法隔开，则输出-1。
吐槽：
我刚开始一看n和m是500，q是n*m，然后判断数据范围是500^3，然后果断判断暴力bfs能过，直接开干，小数据还真过了T_T，结果终测跪了Orz。后来发现其实数据范围是500^4→_→，也就是n*m*q。觉得二分+bfs能过。结果别人说确实能过。然后我自己写了一下，顺利过了。但二分还是写的不熟，中间出了点小差错=_=。
看题解标程居然是并查集，果断给跪，这么吊的思路也是没谁了，而且实现起来也是非常简单的并查集。直接套模板都可以的那种。亏我还专门搞过一段时间的并查集呢，思路还是不够宽广啊，以后脑洞要更大一点才行。嗯，就这么愉快地决定了。
题解：
- 二分+bfs。很好理解，将第一行入队，然后bfs向上下左右瞎jb搜，只要能够搜到最后一行，就表示没有隔开（反之亦然）。二分年限即可。时间复杂度O(n*m*log2(q))；
- 离线并查集，将所有的q保存下来，然后生成最终地图。然后建立初始并查集，将每个通路和它上下左右四个通路连接，创建两个虚节点s1, t1，将第一行所有点连接到s1，将最后一行所有点连接到t1。然后从第q年往回减阻碍，每减一个阻碍就将这个点与它周围所存在的通路合并，直到将s1和t1合并到同一个集合里。然后输出此时的年限即可。时间复杂度为O(n*m+q)。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std; const int N = ; struct Node
{
int x, y;
}; int dis[][] = {{, }, {-, }, {, }, {, -}}; //搜索的方向 int t, n, m, q;
char mp[N][N]; //初始地图
char s[N][N]; //每次搜的地图
bool vis[N][N]; //记忆化剪枝
Node ss[N*N]; //记录（离线）生成出阻碍 bool bfs(int x) //bfs瞎jb搜，能隔开返回0，连通则返回1
{
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++) s[i][j] = mp[i][j];
}
for(int i = ; i < x; i++) s[ss[i].x][ss[i].y] = '';
queue<Node> que;
memset(vis, , sizeof(vis));
for(int i = ; i < m; i++)
{
if(s[][i] == '')
{
Node p;
p.x = ;
p.y = i;
que.push(p);
vis[][i] = ;
}
}
while(!que.empty())
{
Node p = que.front();
que.pop();
Node pp;
for(int i = ; i < ; i++)
{
int dx = p.x+dis[i][];
int dy = p.y+dis[i][];
if(dx >= && dx < n && dy >= && dy < m && s[dx][dy] == '' && vis[dx][dy] == )
{
if(dx == n-) return ;
pp.x = dx;
pp.y = dy;
que.push(pp);
vis[dx][dy] = ;
}
}
}
return ;
} void Init()
{
scanf("%d%d", &n, &m);
for(int i = ; i < n; i++)
{
scanf("%s", mp[i]);
}
scanf("%d", &q);
for(int i = ; i < q; i++) scanf("%d%d", &ss[i].x, &ss[i].y);
} void Work()
{
int l = , r = q-;
if(!bfs(l)) //判断初始能否隔开
{
printf("0\n");
return;
}
if(bfs(r)) //判断最终能否隔开
{
printf("-1\n");
return;
}
bool flag;
while(l < r-) //二分年限
{
int lr = (l+r)/;
flag = bfs(lr);
if(flag) l = lr;
else r = lr;
}
printf("%d\n", r);
} int main()
{
scanf("%d", &t);
for(int tm = ; tm <= t; tm++)
{
Init();
Work();
}
return ;
}
二分+bfs
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; const int N = ; int dis[][] = {{, }, {, -}, {, }, {-, }}; //四个方向搜索 int t;
int n, m;
int q;
char mp[N][N]; //地图
int s[N*N][]; //记录（离线）生成的阻碍
int fm[N*N]; //并查集
int vis[N][N]; //dfs记忆化 int mfind(int x) //并查集查询
{
int fx = x;
while(fx != fm[fx])
{
fx = fm[fx];
}
while(x != fx)
{
int mx = fm[x];
fm[x] = fx;
x = mx;
}
return fx;
} void mmerge(int x, int y) //并查集合并
{
int fx = mfind(x);
int fy = mfind(y);
if(fx != fy) fm[fy] = fx;
} void dfs(int x, int y) //遍历全图
{
int dx, dy;
for(int i = ; i < ; i++)
{
dx = x+dis[i][];
dy = y+dis[i][];
if(dx >= && dx < n && dy >= && dy < m && mp[dx][dy] == '' && !vis[dx][dy])
{
mmerge(x*m+y, dx*m+dy);
vis[dx][dy] = ;
dfs(dx, dy);
}
}
} void Init()
{
scanf("%d%d", &n, &m);
for(int i = ; i < n; i++) scanf("%s", mp[i]);
scanf("%d", &q);
for(int i = ; i < q; i++)
{
scanf("%d%d", &s[i][], &s[i][]);
mp[s[i][]][s[i][]] = '';
}
} void Work()
{ for(int i = ; i < n*m+; i++) fm[i] = i; //并查集预处理
memset(vis, , sizeof(vis)); //记忆化标记
for(int i = ; i < n; i++) //遍历全图，初始化并查集
{
for(int j = ; j < m; j++)
{
if(!vis[i][j] && mp[i][j] == '')
{
vis[i][j] = ;
dfs(i, j);
}
}
} for(int i = ; i < m; i++) //虚节点s1(n*m)与t1(n*m+1)的创建
{
mmerge(n*m, i);
mmerge(n*m+, (n-)*m+i);
}
if(mfind(n*m+) == mfind(n*m)) //始终无法隔开
{
printf("-1\n");
return;
} int p; //第p+1年隔开
bool flag = ; //临时标记，退出循环的判断
for(p = q-; p >= ; p--)
{
int dx, dy;
int xx = s[p][];
int yy = s[p][];
mp[xx][yy] = '';
for(int i = ; i < ; i++)
{
dx = xx+dis[i][];
dy = yy+dis[i][];
if(dx >= && dx < n && dy >= && dy < m && mp[dx][dy] == '')
{
mmerge(dx*m+dy, xx*m+yy);
if(mfind(n*m+) == mfind(n*m))
{
flag = ;
break;
}
}
}
if(flag) break;
}
if(flag) printf("%d\n", p+);
else printf("0\n");
} int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &t);
for(int tm = ; tm <= t; tm++)
{
Init();
Work();
}
}
并查集