I’m stuck!

GitHub跳转原题关系图 Canvas 关系图返回列表

把方向受限地图建成有向图，分别从 S 正向搜索和从 T 在反图搜索，再统计可达集合差集。

OJ: shumeng

题目 ID: CSP201312E

难度:普及+/提高-

标签:图BFS反图可达性网格

日期: 2026-07-31 16:21

形式化题目

给定 $R\times C$ 的网格，每个非障碍格子按自身字符决定下一步能走的四个方向。设 $A$ 为从起点 S 出发可达的格子集合。若 S 无法到达 T，输出 I'm stuck!；否则统计 $A$ 中不能到达目标 T 的格子数。

思路

先看直接按照定义判断的朴素做法：

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
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:49
 */
// brute.cpp：小数据暴力解，对每个从 S 可达的格子单独搜索 T。
#include <bits/stdc++.h>
using namespace std;

const int MAXR = 55;
const int MAXC = 55;

int R, C;
char grid[MAXR][MAXC];
bool from_start[MAXR][MAXC], vis[MAXR][MAXC];
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

bool inside(int r, int c) {
    return r >= 1 && r <= R && c >= 1 && c <= C;
}

bool allow_direction(char cell, int direction) {
    if (cell == '-' && direction < 2) {
        return false;
    }
    if (cell == '|' && direction >= 2) {
        return false;
    }
    if (cell == '.' && direction != 1) {
        return false;
    }
    return true;
}

void bfs_mark_start(int start_r, int start_c) {
    queue<pair<int, int> > q;
    from_start[start_r][start_c] = true;
    q.push(make_pair(start_r, start_c));

    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();

        int r = now.first;
        int c = now.second;
        for (int direction = 0; direction < 4; direction++) {
            if (!allow_direction(grid[r][c], direction)) {
                continue;
            }

            int nr = r + dr[direction];
            int nc = c + dc[direction];
            if (!inside(nr, nc) || grid[nr][nc] == '#' || from_start[nr][nc]) {
                continue;
            }

            from_start[nr][nc] = true;
            q.push(make_pair(nr, nc));
        }
    }
}

bool can_reach_target(int start_r, int start_c, int target_r, int target_c) {
    memset(vis, 0, sizeof(vis));
    queue<pair<int, int> > q;
    vis[start_r][start_c] = true;
    q.push(make_pair(start_r, start_c));

    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();

        int r = now.first;
        int c = now.second;
        if (r == target_r && c == target_c) {
            return true;
        }

        for (int direction = 0; direction < 4; direction++) {
            if (!allow_direction(grid[r][c], direction)) {
                continue;
            }

            int nr = r + dr[direction];
            int nc = c + dc[direction];
            if (!inside(nr, nc) || grid[nr][nc] == '#' || vis[nr][nc]) {
                continue;
            }

            vis[nr][nc] = true;
            q.push(make_pair(nr, nc));
        }
    }

    return false;
}

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

    cin >> R >> C;
    int start_r = 0, start_c = 0, target_r = 0, target_c = 0;
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            cin >> grid[r][c];
            if (grid[r][c] == 'S') {
                start_r = r;
                start_c = c;
            }
            if (grid[r][c] == 'T') {
                target_r = r;
                target_c = c;
            }
        }
    }

    bfs_mark_start(start_r, start_c);
    if (!from_start[target_r][target_c]) {
        cout << "I'm stuck!\n";
        return 0;
    }

    int answer = 0;
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            if (from_start[r][c] && !can_reach_target(r, c, target_r, target_c)) {
                answer++;
            }
        }
    }

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

它先从 S 搜索所有可达格子，再对每个这样的格子单独搜索 T。若有 $V$ 个格子、 $E$ 条合法移动边，最坏会重复做 $V$ 次图搜索，复杂度为 $O(V(V+E))$ 。

反图搜索

令 $A$ 为从 S 在原图可达的格子集合。题目第二个性质需要判断某格能否到达 T，这正是反图搜索的用途：把每条边反向后，从 T 搜索得到的集合 $B$ ，恰好是原图中可以到达 T 的格子。

因此先做原图 BFS 得到 from_start。若 T 不在其中，按题意输出 I'm stuck!。否则建反图并从 T BFS 得到 to_target，答案就是：

|A\setminus B|

也就是遍历所有格子，统计 from_start[r][c] && !to_target[r][c]。S、T 与 + 都有四个方向的出边；- 只允许左右，| 只允许上下，. 只允许向下。

样例双向可达性

下表把官方样例的格子按可达性分类：B 表示既能从 S 到达又能到达 T，X 表示只能从 S 到达，R 表示只能到达 T，# 是障碍。

行/列	1	2	3	4	5
1	B	B	B	B	B
2	R	R	B	#	X
3	B	R	B	#	#
4	B	B	B	B	B
5	#	#	#	#	X

两个 X 都在集合 $A$ 中却不在集合 $B$ 中，所以样例答案为 2。R 格虽然可到达 T，但从 S 不能进入，不满足第一个性质。这也说明正向与反向两次搜索不能互相替代：它们分别回答题目的两个方向问题。

代码

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
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:49
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXR = 55;
const int MAXC = 55;

int R, C;
char grid[MAXR][MAXC];
bool from_start[MAXR][MAXC], to_target[MAXR][MAXC];
vector<pair<int, int> > reverse_edge[MAXR][MAXC];

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

bool inside(int r, int c) {
    return r >= 1 && r <= R && c >= 1 && c <= C;
}

bool allow_direction(char cell, int direction) {
    if (cell == '-' && direction < 2) {
        return false;
    }
    if (cell == '|' && direction >= 2) {
        return false;
    }
    if (cell == '.' && direction != 1) {
        return false;
    }
    return true;
}

void bfs_from_start(int start_r, int start_c) {
    queue<pair<int, int> > q;
    from_start[start_r][start_c] = true;
    q.push(make_pair(start_r, start_c));

    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();

        int r = now.first;
        int c = now.second;
        for (int direction = 0; direction < 4; direction++) {
            if (!allow_direction(grid[r][c], direction)) {
                continue;
            }

            int nr = r + dr[direction];
            int nc = c + dc[direction];
            if (!inside(nr, nc) || grid[nr][nc] == '#' || from_start[nr][nc]) {
                continue;
            }

            from_start[nr][nc] = true;
            q.push(make_pair(nr, nc));
        }
    }
}

void bfs_to_target(int target_r, int target_c) {
    queue<pair<int, int> > q;
    to_target[target_r][target_c] = true;
    q.push(make_pair(target_r, target_c));

    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();

        int r = now.first;
        int c = now.second;
        for (int i = 0; i < (int)reverse_edge[r][c].size(); i++) {
            int pre_r = reverse_edge[r][c][i].first;
            int pre_c = reverse_edge[r][c][i].second;
            if (to_target[pre_r][pre_c]) {
                continue;
            }

            to_target[pre_r][pre_c] = true;
            q.push(make_pair(pre_r, pre_c));
        }
    }
}

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

    cin >> R >> C;
    int start_r = 0, start_c = 0, target_r = 0, target_c = 0;

    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            cin >> grid[r][c];
            if (grid[r][c] == 'S') {
                start_r = r;
                start_c = c;
            }
            if (grid[r][c] == 'T') {
                target_r = r;
                target_c = c;
            }
        }
    }

    // 建反图：原图中 (r, c) 能到 (nr, nc)，就记录其反向前驱。
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            if (grid[r][c] == '#') {
                continue;
            }
            for (int direction = 0; direction < 4; direction++) {
                if (!allow_direction(grid[r][c], direction)) {
                    continue;
                }

                int nr = r + dr[direction];
                int nc = c + dc[direction];
                if (!inside(nr, nc) || grid[nr][nc] == '#') {
                    continue;
                }
                reverse_edge[nr][nc].push_back(make_pair(r, c));
            }
        }
    }

    bfs_from_start(start_r, start_c);
    if (!from_start[target_r][target_c]) {
        cout << "I'm stuck!\n";
        return 0;
    }

    bfs_to_target(target_r, target_c);
    int answer = 0;
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            if (from_start[r][c] && !to_target[r][c]) {
                answer++;
            }
        }
    }

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

复杂度

每个格子最多有 4 条边，建图、两次 BFS 与统计共需 $O(V+E)=O(RC)$ 时间，反图和访问数组使用 $O(V+E)$ 空间。

总结

遇到单向移动规则时，先把网格看成有向图。要同时判断“从起点能到”和“能到终点”，分别做一次正向搜索和一次从终点出发的反图搜索，再取集合差即可。

图示解析

这张图串起本题从地图规则到统计答案的主线：

text

1
2
3
4
5每个格子按自身字符决定有向边
|- 从 S 正向搜索，得到集合 A：S 能到达的格子
`- 建立反图后从 T 搜索，得到集合 B：能到达 T 的格子
   |- T 不在 A 中：输出 I'm stuck!
   `- 否则统计 A 中不属于 B 的格子

反图中的搜索方向翻转了原图每一条边，因此从 T 反向可达恰好等价于原图中可以到达 T。两个集合分别对应题目的两个性质，取差集不需要从每个格子重复搜索。每个格子和每条可能移动边只处理常数次。

时间限制： 1.0 秒

空间限制： 256 MB

题目描述

给定一个 $R$ 行 $C$ 列的地图，地图的每一个方格可能是 #、+、-、|、.、S、T 七个字符中的一个，分别表示如下意思：

#：任何时候玩家都不能移动到此方格；
+：当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非 # 方格移动一格；
-：当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非 # 方格移动一格；
|：当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非 # 方格移动一格；
.：当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为 #，则玩家不能再移动；
S：玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非 # 方格移动一格；
T：玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非 # 方格移动一格。

此外，玩家不能移动出地图。

请找出满足下面两个性质的方格个数：

玩家可以从初始位置移动到此方格；
玩家不可以从此方格移动到目标位置。

输入格式

从标准输入读入数据。

输入的第一行包括两个整数 $R$ 和 $C$ ，分别表示地图的行和列数。

接下来的 $R$ 行，每行都包含 $C$ 个字符，表示地图的格子。保证地图上有且只有一个 S 和一个 T。

输出格式

输出到标准输出。

如果玩家在初始位置就已经不能到达终点了，就输出 I'm stuck!；否则的话，输出满足性质的方格的个数。

input1

1
2
3
4
5
65 5
--+-+
..|#.
..|##
S-+-T
####.

output1

样例 1 解释

如果把满足性质的方格在地图上用 X 标记出来的话，地图如下所示：

plain

1
2
3
4
5--+-+
..|#X
..|##
S-+-T
####X

数据范围

对于所有数据，保证 $1\le R,C\le 50$ 。

I’m stuck!

目录

形式化题目

思路

反图搜索

样例双向可达性

代码

复杂度

总结

图示解析