题目链接：看这里吧，中文题 解法： 以前做过，BC的一道题，今天复习并查集重写一次。 然后比较显然的就是二分+判断是否连通，判断是否连通用并查集和bfs都可以。
//HDU 5652#include <bits/stdc++.h>using namespace std;const int maxn = 510;int n, m, q, vis[maxn][maxn];char s[maxn][maxn];pair <int, int> d[maxn*maxn];int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};namespace dsu{ int fa[maxn*maxn]; inline void init(){for(int i = 0; i <= n*m + 1; i++) fa[i] = i;} inline int find_set(int x){if(x == fa[x]) return x; else return fa[x] = find_set(fa[x]);} inline void union_set(int x, int y){x = find_set(x), y = find_set(y); if(x != y) fa[x] = y;}}using namespace dsu;int check(int t){ init(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(s[i][j] == '1') vis[i][j] = 1; else vis[i][j] = 0; for(int i = 1; i <= t ;i++){ vis[d[i].first][d[i].second] = 1; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(vis[i][j] == 1) continue; for(int k = 0; k < 4; k++){ int tx = i + dir[k][0], ty = j + dir[k][1]; if(ty <= 0 || ty > m) continue; if(tx == 0) union_set((i-1)*m + j, 0); else if(tx == n+1) union_set((i-1)*m + j, n*m+1); else{ if(vis[tx][ty]) continue; union_set((i-1)*m + j, (tx-1)*m+ty); } } } } if(find_set(0) == find_set(n*m+1)) return 1; else return 0;}int main(){ int T; scanf("%d", &T); while(T--){ memset(vis, 0, sizeof(vis)); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%s", s[i]+1); scanf("%d", &q); for(int i = 1; i <= q; i++){ scanf("%d%d", &d[i].first, &d[i].second); d[i].first++, d[i].second++; } if(check(q)){ puts("-1"); return 0; } int l = 0, r = q , ans = 0; while(l <= r){ int mid = (l + r ) / 2; if(!check(mid)) r = mid - 1, ans = mid; else l = mid + 1; } PRintf("%d/n", ans); } return 0;}新闻热点
疑难解答
