Contents

1. 1. Sample Input
2. 2. Sample Output
3. 3. 分析：
4. 4. 正解：

Sample Input

1
4 6
011010
000010
100001
001000
7
0 3
1 5
1 3
0 0
1 2
2 4
2 1

Sample Output

4

分析：

• 并查集 + BFS
• 设两个特殊点，看他们啥时候连通
• 具体还是看代码吧，用代码说话

正解：

#include <cstdio>
#include <cstring>
#define MAXN 510
int father[MAXN * MAXN], ranks[MAXN * MAXN];  //二维转一维做
int l = MAXN * MAXN - 1, r = MAXN * MAXN - 2;  //左右两个特殊点
bool mp[MAXN][MAXN];
int vec[8][2] = {{-1,0},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1},{1,0},{0,1}};
// 八个方向

void init_set(){

    for(int i = 0; i < MAXN * MAXN; i++){
        father[i] = i;
        ranks[i] = 1;
    }
    for(int i = 0; i < MAXN; i++)
    {
        for(int j = 0; j < MAXN; j++)
            mp[i][j] = false;
    }
}

int find_set(int x){

    return father[x] == x ? father[x] : father[x] = find_set(father[x]);
}

void union_set(int x, int y){

    if(ranks[x] > ranks[y]){
        father[y] = x;
    }
    else if(ranks[x] < ranks[y]){
        father[x] = y;
    }
    else{
        father[y] = x;
        ranks[x]++;
    }
}

int main(){

    //freopen("input.txt", "r", stdin);
    int T, q, x, y, ii, jj, n, m;
    scanf("%d", &T);
    getchar();
    while(T--){
        scanf("%d%d", &n, &m);
        init_set();
        getchar();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(mp[i][j] = getchar() == '1'){
                    if(j == 0)
                        union_set(find_set(l), find_set(i * m + j));
                    else if(j == m - 1)
                        union_set(r, i * m + j);
                    for (int k = 0; k < 8; ++k)
                    {
                        ii = i + vec[k][0];
                        jj = j + vec[k][1];
                        if (ii >= 0 && ii < n && jj >= 0 && jj < m && mp[ii][jj])
                            union_set(find_set(ii * m + jj), find_set(i * m + j));
                    }
                }
            }
            getchar();
        }
        scanf("%d", &q);
        int year, ans = -1;
        for(year = 1; year <= q; ++year){
            scanf("%d%d", &x, &y);
            if (~ans)				//~是取反操作，如果ans不等于-1，
                continue;
            mp[x][y] = true;

            if (y == 0)
                union_set(x * m + y, l);
            else if (y == m - 1)
                union_set(x * m + y, r);
            for (int k = 0; k < 8; ++k)
            {
                ii = x + vec[k][0];
                jj = y + vec[k][1];
                if (ii >= 0 && ii < n && jj >= 0 && jj < m && mp[ii][jj])
                    union_set(find_set(ii * m + jj), find_set(x * m + y));
            }
            //printf("%d %d\n", find_set(l), find_set(r));
            if(find_set(l) == find_set(r))	//看左右两个特殊点啥时候连通
                ans = year;
            //这里我第一次做的时候犯了个错误,加了break,这样的话第一组数据到4的时候跳出
            //输入流里还有数据，结果和第二组数据一起输入了
        }
        printf("%d\n", ans);
    }
    return 0;
}