题目链接：http://acm.hust.edu.cn/vjudge/contest/128683#problem/E
题目大意：给定一只含有0和1的地图，0代表可以走的格子，1代表不能走的格
子。之后过了M年，每年把一个格子变成1， 即每年会有一个格子不能走。问地
图上界和下界连通共多少年。如果到M年之后依然连通，则输出-1.
给定的年份数据范围是10^5， 图的大小是500*500，由于图是一直在改变的，
因此每次都需要进行变更操作。然而如果变更一次广搜一次明显会TLE。仔细思
考会发现，当某一年上下界不再连通时，之后的所有年份必定不会连通；如果某
年上下界依然连通，则此年之前的所有年份都是连通的（因为此年是以前的年份
时的地图再封杀一些后得到的）。这么想之后可以发现寻找不连通的那一年可以
通过二分查找来实现。一些神犇的题解报告都是用并查集过的，然而蒟蒻的并查
集实在是太渣了...暴力解题出奇迹。
下面是AC代码：
/** Memory: 3308 KB Time: 1216 MS Language: G++ Result: Accepted **/ #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> using namespace std; int n, m, x[500000], y[500000], vis[550][550]; char maps[550][550]; int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; struct ad { int x, y; }; bool bfs(int x, int y) { queue<ad>Q; ad now, next; memset(vis, 0, sizeof(vis)); now.x = x; now.y = y; vis[now.x][now.y] = 1; Q.push(now); while(Q.size()) { now = Q.front(); Q.pop(); if(now.x==n-1)return true; for(int i=0; i<4; i++) { next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1]; if(next.x>=0 && next.x<n && next.y>=0 && next.y<m && maps[next.x][next.y]=='0' && !vis[next.x][next.y]) { vis[next.x][next.y] = 1; Q.push(next); } } } return false; } bool check() { for(int i=0; i<m; i++) { if(maps[0][i]=='0' && bfs(0, i)) return true; } return false; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d %d", &n, &m); for(int i=0; i<n; i++) scanf("%s", maps[i]); int t; scanf("%d", &t); for(int i=1; i<=t; i++) scanf("%d %d", &x[i], &y[i]); int l = 1, r = t, mid, ans = -1; while(l<=r) { mid = (l+r)/2; for(int i=1; i<=mid; i++) maps[x[i]][y[i]] = '1'; if(check()) l = mid + 1; else { ans = mid; r = mid-1; } for(int i=1; i<=mid; i++) maps[x[i]][y[i]] = '0'; } printf("%d ", ans); } return 0; }