[USACO15DEC] Switching on the Lights S

题意

有一个 N x N 的房间网格。

一开始只有 (1,1) 这个房间的灯是亮的，Bessie 也在这里，并且只能走到亮着灯的房间里。

每个房间里可能有若干开关，可以打开别的房间的灯。

问最后最多能打开多少个房间的灯。

思路

先看一个更直观的对照写法：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m;
vector<pair<int, int> > sw[MAXN][MAXN];
bool light_on[MAXN][MAXN];
bool reachable[MAXN][MAXN];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool inside(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        sw[a][b].push_back(make_pair(c, d));
    }

    light_on[1][1] = true;
    reachable[1][1] = true;

    while (true) {
        bool changed = false;

        // 枚举当前所有已经能到达的房间，尝试打开更多灯。
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= n; y++) {
                if (!reachable[x][y]) {
                    continue;
                }
                for (int i = 0; i < (int)sw[x][y].size(); i++) {
                    int tx = sw[x][y][i].first;
                    int ty = sw[x][y][i].second;
                    if (!light_on[tx][ty]) {
                        light_on[tx][ty] = true;
                        changed = true;
                    }
                }
            }
        }

        // 只要房间被点亮并且挨着已达房间，就能变成新的可达房间。
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= n; y++) {
                if (!light_on[x][y] || reachable[x][y]) {
                    continue;
                }
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if (inside(nx, ny) && reachable[nx][ny]) {
                        reachable[x][y] = true;
                        changed = true;
                        break;
                    }
                }
            }
        }

        if (!changed) {
            break;
        }
    }

    int ans = 0;
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++) {
            if (light_on[x][y]) {
                ans++;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

brute.cpp 的思路是反复做两件事：

从当前所有已达房间出发，把能打开的灯都打开；
看看有没有新亮房间因为挨着已达区域而变成新的可达房间。

只要这一轮还有变化，就继续循环。

这个写法能帮助理解题意，但正式解更适合直接用 BFS。

这题的核心是把两个概念分开：

light_on[x][y]：这个房间的灯是否已经亮
visited[x][y]：这个房间现在是否已经真的能走进去

注意：

房间灯亮了，不代表现在一定能走到
但只要一个亮灯房间挨着已访问区域，它就会立刻变成可达房间

所以 BFS 过程是：

初始只有 (1,1) 亮灯且可达
访问到一个房间 (x,y) 时，先打开它控制的所有灯
某个新亮房间如果已经挨着访问区域，就马上入队
再从 (x,y) 继续走向四周所有“亮灯但未访问”的房间

这样可达区域和亮灯区域会不断连锁扩张，直到队列为空。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXM = 20005;

int n, m;
vector<pair<int, int> > sw[MAXN][MAXN];
bool light_on[MAXN][MAXN];
bool visited[MAXN][MAXN];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool inside(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

bool has_visited_neighbor(int x, int y) {
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (inside(nx, ny) && visited[nx][ny]) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        sw[a][b].push_back(make_pair(c, d));
    }

    queue<pair<int, int> > q;
    light_on[1][1] = true;
    visited[1][1] = true;
    q.push(make_pair(1, 1));

    int ans = 1;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        int x = cur.first;
        int y = cur.second;

        // 到达房间后，把这个房间能控制的灯全部打开。
        for (int i = 0; i < (int)sw[x][y].size(); i++) {
            int tx = sw[x][y][i].first;
            int ty = sw[x][y][i].second;

            if (!light_on[tx][ty]) {
                light_on[tx][ty] = true;
                ans++;

                // 新点亮的房间如果已经挨着可达区域，就能立刻走进去。
                if (!visited[tx][ty] && has_visited_neighbor(tx, ty)) {
                    visited[tx][ty] = true;
                    q.push(make_pair(tx, ty));
                }
            }
        }

        // 从当前房间继续走向四周所有“已点亮但还没访问”的房间。
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (!inside(nx, ny)) {
                continue;
            }
            if (!light_on[nx][ny] || visited[nx][ny]) {
                continue;
            }
            visited[nx][ny] = true;
            q.push(make_pair(nx, ny));
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

每个房间最多入队一次，每条开关信息最多处理一次。

所以总时间复杂度是：

$O(N^2 + M)$

空间复杂度也是：

$O(N^2 + M)$

总结

这题最关键的一步就是想清楚：

灯亮
可达

不是一回事。

一旦把这两个状态分开，再配合 BFS 维护“新可达房间”，整题就很顺了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[USACO15DEC] Switching on the Lights S

目录

题意

思路

代码

复杂度

总结

一图流解析