题目链接：看这里吧，中文题
解法： 以前做过，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;
}