2021计蒜之道 – 精英组 – 预赛第三场 – T3

题目链接

2021计蒜之道 – 预赛 – wy的单机游戏

题目描述

给定一个 $n$ 行 $m$ 列的矩阵,矩阵中可能有三种字符:

  1. # 表示墙,不能移动到墙上。
  2. . 表示可以行走的空地。
  3. 英文大写字母表示传送门的序号,传送门成对出现,每个字母若出现,则仅出现两次。

玩家每秒可以向上、下、左、右移动一格,不能移动到墙上,也不能呆在原地不动

在行走过程中,玩家如果走到了传送门上,无法选择是否传送,必然在一瞬间被传送到另一个与其配对的传送门处。

设两个配对的传送门 $A$ 分别为 $A_1$ 和 $A_2$,则当玩家踏入 $A_1$ 的瞬间,就会被传送到 $A_2$ 处,这个过程不消耗时间。但在传送到 $A_2$ 后,$A_2$ 传送门会失效一秒钟,不能直接回到传送门 $A_1$.

每次游戏,玩家出生在 $(1, 1)$,需要到达终点 $(n, m)$,求最少花费时间。

$1\leq n, m\leq 100$.

题目解释

例如下面的地图:

.#.
A#A
.#.

玩家从 $(1, 1)$ 走到 $(3, 1)$ 的其中一种合法方案为:

$$
(1, 1)\rightarrow (2, 1)\rightarrow(2, 3)\rightarrow(1, 3)\rightarrow(2, 3)\rightarrow(2, 1)\rightarrow(3, 1)
$$

而这是一种不合法的方案:

$$
(1, 1)\rightarrow(2, 1)\rightarrow(3, 1)
$$

因为碰到传送门必定被传送走。

题目分析

不难想到最短路,考虑如何建图。

要特殊处理的地方是:穿过传送门后的一秒。在这一秒,不能走回原来的传送门,只能走向其他点,而下一秒还可以再回来。

想到建立分层图对传送门进行处理。将传送门节点复制一份,放到第二层。此时第一层的传送门节点,代表的是还未被传送走的状态,而第二层的传送门节点,代表被传送到这个传送门之后的状态。

建图方式:

所以,与传送门相邻的节点可以到达第一层,但不能到达第二层;第一层的传送门节点不能到达与其相邻的节点(因为一定会被传走),而第二层的传送门节点可以到达与其相邻的节点。若同一层的两个传送门之间不相邻,则互相不可到达。

形式化地:

不妨设一对传送门分别为 $A_1$ 和 $A_2$,将所有传送门节点复制到第二层,复制后的节点叫 $B_1$ 和 $B_2$,传送门 $A_1$ 与空节点 $x$ 相邻。则:

传送门之间连边的方式为 $A_1\rightarrow B_2$,$A_2\rightarrow B_1$.

传送门与相邻节点之间连边的方式为:$x\rightarrow A_1$,$B_1\rightarrow x$.

这样建图之后,点数为最多为 $n^2+26\times 2$,边数也大概在 $n^2$ 量级。这样用堆优化的 Dijkstra 求出最短路即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 108;
int n, m;
char in[MAXN][MAXN];
int get(int x, int y) {//对坐标(x, y)做hash
    return (x - 1) * m + y;
}
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
struct Edge{
    int to, nxt, val;
}edge[(MAXN * MAXN) << 4];
int head[(MAXN * MAXN) << 1], e_cnt = 0;
void add(int u, int v, int w) {
    edge[++e_cnt].to = v;
    edge[e_cnt].val = w;
    edge[e_cnt].nxt = head[u];
    head[u] = e_cnt;
}
pair<int, int> door[30][2];
//door[i][0]存储的是,第i组传送门的第一个点的坐标,door[i][1]是第二个点的坐标
int dis[(MAXN * MAXN) << 1];
bool vis[(MAXN * MAXN) << 1];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
void Dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    q.push(make_pair(0, 1));
    while(!q.empty()) {
        int id = q.top().second; q.pop();
        if(vis[id]) continue;
        vis[id] = true;
        for(int i = head[id]; i; i = edge[i].nxt) {
            int ne = edge[i].to, val = edge[i].val;
            if(dis[ne] > dis[id] + val) {
                dis[ne] = dis[id] + val;
                q.push(make_pair(dis[ne], ne));
            }
        }
    }
}
signed main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        cin >> (in[i] + 1);
    }
    //处理传送门:
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(in[i][j] >= 'A' && in[i][j] <= 'Z') {
                int num = in[i][j] - 'A' + 1;
                if(door[num][0].first == 0) {//第一次遇到
                    door[num][0] = make_pair(i, j);
                } else {//第二次遇到,传送点之间跨层连边,即A1向B2连边,A2向B1连边
                    add(get(i, j), get(door[num][0].first, door[num][0].second) + n * m, 0);
                    add(get(door[num][0].first, door[num][0].second), get(i, j) + n * m, 0);
                }
            }
        }
    }
    //处理空白点相关:
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(in[i][j] == '#') continue;
            else if(in[i][j] == '.') {//对于空白点,可以向相邻的,第一层传送门/空白点连边
                for(int k = 0; k < 4; k++) {
                    int nx = i + dir[k][0], ny = j + dir[k][1];
                    if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
                    if(in[nx][ny] == '.') add(get(i, j), get(nx, ny), 1);
                    else if(in[nx][ny] != '#') {
                        add(get(i, j), get(nx, ny), 1);
                    }
                }
            } else {//对于传送门点,将第二层的传送门点向第一层相邻所有能走到的点连边
                for(int k = 0; k < 4; k++) {
                    int nx = i + dir[k][0], ny = j + dir[k][1];
                    if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
                    if(in[nx][ny] != '#') {
                        add(get(i, j) + n * m, get(nx, ny), 1);
                    }
                }
            }
        }
    }
    Dijkstra();
    if(dis[get(n, m)] >= 0x3f3f3f3f && dis[get(n, m) + n * m] >= 0x3f3f3f3f)//无法到达
        cout << "Game Over." << endl;
    else cout << min(dis[get(n, m)], dis[get(n, m) + n * m]) << endl;
    return 0;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇