丑单2023秋招笔试第二题 我好想逃却到不掉.jpg (C++ DFS)

题目(请先认真读完)

曾经的我不过是一介草民，混迹市井，默默无名。直到我被罗马的士兵从家乡捉走丢进竞技场……对手出现了，我架紧盾牌想要防御，只觉得巨大的冲击力有如一面城墙冲涌而来，击碎了我的盾牌，我两眼发昏，沉重的身躯轰然倒地。
——我好想逃
但罗马最大的竞技场，哪有这么容易逃得掉。工程师们早就在地上装了传送机关，虽不会伤人，却会令站在上面的人传到已指向的位置。若是几个传送机关围成一个环，不小心踩在上面的人就会被一一圈圈地反复传送到这里，我不由得打了个寒颤。必须避开这些危险的地方！

输入描述：

第一行街入两个整数 $n$ 和 $m$，表示迷宫的长和宽
接下来 $n$ 行，每行 $m$ 个字符，用于描述迷宫构造，每个字符可能为以下几种

• . (小数点)表示空地，玩家在空地时可以选择往 [上，下，左，右] 中的某个方问移动一格
• U, D, L, R 分别表示朝向 [上, 下，左, 右]的传送带，站在传送带上的人会被强制移动到其指向的下一个位置
• • 如果下一个位器还是传送带，会被继续传下去
• • 如果传送带指向迷宫外，玩家会撞在墙上昏过去，游戏结束
• O (大写字母O) 表示迷宫出口

输出描述：

输出一个数字，表示迷宫中有多少个位置，当玩家处于此时，无论接下来如何移动都无法再到达出口
（传送带，空地，出口都算一个位置）

示例

输入

5 5
.....
.RRD.
.U.DR
.ULL.
....O
1
2
3
4
5
6

输出

10
1

备注：

$1\le n,m\le 10^5$
$1\le n\ast m\le 10^5$
保证每个迷宫有且仅有一个出口

分析

出不去的点，题目说了是“成环”，事实真的是如此……吗？

成环情况

不成环情况 1

不成环情况 2

黑线是迷宫左下角边界，O是出口，即便不成环，依然走不到出口。

临时总结：题目在隐隐约约误导你。

反方向解决

到达不了出口的位置不好判断，那我们把能到达出口的数量 $ans$ 找出来，$n\ast m-ans$ 就是我们要的结果，那好找吗？
以玩游戏“耍赖”的经验，直接从迷宫出口往回走，反着走能到达的地方，就是我们要的 $ans$。

对于空地

反向侦查时，空地类型，和指向自己的传送带都可以进一步侦查。

⚠️对于传送带

反向侦查时，传送带，只能进一步侦查指向自己的传送带。
基本的DFS就可以解决，用一个bool type表示当前节点的种类。

⚠️迷宫二维数组的存储

这个也是个大陷阱，如果用常规的int map[n][m]，按先 $x$ 后 $y$ 的写法，map[x][y]对吗，是我们数学的坐标系概念中，对应的点 $(x,y)$ 吗？仔细想一想，好像不是吧。

$n$ 对应的不是 $x$, 是 $y$ ，数组中说 $n$ “行”，$m$ “列”，但是在这个2维的坐标系中，分别对应的是 $y$ 坐标和 $x$ 坐标。这一步做错，后边的逻辑再对，结果也总是差那么一点，可惜，在最后才发现，但是已经晚了。

for(int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		con >> mp[i][j];
	}
} // 像这样存储迷宫图, 就会逻辑复杂, 错错错
1
2
3
4
5

代码

#include 
#include 

using namespace std;

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

char arrow[4] = {'R', 'D', 'L', 'U'};
// 存储 反方向 箭头
// dx[0], dy[0]指向左边,
// 那对应的箭头就应该指向右边, 所以是”R”
// 其余同理

int n, m;
int ox, oy; // 出口

unsigned long ans = 1; // 出口本身就能到达出口

void dfs(vector<vector<pair<char, int>>> &mp, int x, int y, bool type) {
    for (int i = 0; i < 4; i ++) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 0 || tx >= n || ty < 0 || ty >= m) 
            continue;
        if (mp[tx][ty].second == 1)
            continue;
        if (type && '.' == mp[tx][ty].first){ // 空地可以反向侦查两种类型
            ans++;
            mp[tx][ty].second = 1;
            dfs(mp, tx, ty, true); // 接下来可能遍历传送带, 也可能是空地
        }
        if (arrow[i] == mp[tx][ty].first) { // 传送带只能反向侦查指向自己的传送带
            ans++;
            mp[tx][ty].second = 1;
            dfs(mp, tx, ty, false); // 接下来遍历的都会是传送带
        }
    }
}

int main() {
    cin >> n >> m;
    vector<vector<pair<char, int>>> mp(m, vector<pair<char, int>>(n, make_pair(' ', 0)));
    // 二维数组 不是 mp[n][m]
    // 而是为了书写方便, 改成的 mp[m][n]
    // 存储 (字符, 访问位)
    for (int j = n - 1; j >= 0; j--) {
    	// 	第一行, 其实是最高的 y 坐标
        string s;
        cin >> s;
        for (int i = 0; i < m; i++) {
            if (s[i] == 'O') {
                ox = i;
                oy = j;
                mp[i][j].second = 1;
            }
            mp[i][j].first = s[i];
        }
    }
    dfs(mp, ox, oy, true);
    cout << n * m - ans;
    return 0;
}
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