洛谷P1141《01迷宫》

一月 10, 2019 4045

DFS 联通块

题目描述

有一个仅由数字 0 与 1 组成的 n \times n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入输出格式

输入格式

第11行为两个正整数 n,m 。

下面 n 行，每行 n 个字符，字符只可能是 0 或者 1 ，字符之间没有空格。

接下来 m 行，每行 2 个用空格分隔的正整数 i,j ，对应了迷宫中第 i 行第 j 列的一个格子，询问从这一格开始能移动到多少格。

输出格式

m 行，对于每个询问输出相应答案。

输入输出样例

输入样例

1
2
3
4
5
2 2
01
10
1 1
2 2

输出样例

1
2
4
4

说明

所有格子互相可达。

对于 20\%20 的数据， n≤10 ；

对于 40\% 的数据， n≤50 ；

对于 50\% 的数据， m≤5 ；

对于 60\% 的数据， n≤100,m≤100 ；

对于 100\% 的数据， n≤1000,m≤100000 。

解题思路

首先我们可以知道一个联通块内的所有格子的答案相同

那么我们就直接找联通块，这个联通块内的所有格子的答案都是这个联通块的格子个数

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int dx[] = {0, 1, -1, 0, 0};
    const int dy[] = {0, 0, 0, -1, 1};
    const int MAXN = 1000 + 10;
    
    char mp[MAXN][MAXN];
    bool vis[MAXN][MAXN];
    
    int n, m, nowans;
    int xans[MAXN * MAXN], yans[MAXN * MAXN];
    int ans[MAXN][MAXN];
    
    void Search(int x, int y) {
        ++nowans;
        xans[nowans] = x;
        yans[nowans] = y;
        for (int i = 1; i <= 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (!(nx <= 0 || nx > n || ny <= 0 || ny > n) && !vis[nx][ny] && mp[nx][ny] != mp[x][y]) {
                vis[nx][ny] = true;
                Search(nx, ny);
            }
        }
    }
}

signed main() {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    using namespace FastIO;
    scanf("%d %d", &n, &m);
    For (i, 1, n) {
        scanf("%s", mp[i] + 1);
    }
    For (i, 1, n) {
        For (j, 1, n) {
            if (!vis[i][j]) {
                vis[i][j] = true;
                nowans = 0;
                Search(i, j);
                for (int no = 1; no <= nowans; ++no) {
                    ans[xans[no]][yans[no]] = nowans;
                }
            }
        }
    }
    For (i, 1, m) {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", ans[x][y]);
    }
    return 0;
}