[ABC176D] Wizard in Maze

· · 题解

[ABC176D] Wizard in Maze 题解

题目面板(洛谷)

化繁为简

对于题目的描述，我们可以总结出两种移动方式：

现在，我们不考虑第二种移动方式，只考虑第一种。那这第一种移动方式就是广搜的模版代码，直接给出：

#include<bits/stdc++.h>
using namespace std;
int n, m, sc, sr, ec, er;
char a[1005][1005];
int vis[1005][1005];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
struct node {
    int x, y;
};
void bfs() {
    queue<node>d;
    d.push((node) { sc, sr });
    vis[sc][sr] = 1;
    while (!d.empty()) {
        node q = d.front();
        d.pop();
        for (int i = 0; i < 4; i++) {
            int nx = q.x + dir[i][0], ny = q.y + dir[i][1];
            if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && vis[nx][ny] && a[nx][ny] == '.') {
                d.push((node) { nx, ny });
                vis[nx][ny] = 1;
            }
        }
    }
}
int main() {
    cin >> n >> m >> sc >> sr >> ec >> er;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    bfs();
    if (!vis[ec][er])cout << "-1\n";
    else cout << vis[ec][er] << "\n";
    return 0;
}

接下来我们将考虑第二种移动方式。

优先级划分

请读者思考一下，上面提到的两种移动方法哪一种的优先级更高呢？

由于题目中说“最少使用几次魔法才能到位置”，所以不用魔法的移动方式显然优先级更高，即第一种方法优先级更高。

普通队列升级

既然第一种移动方式优先级更高，那么我们每次执行第一种移动方式时都应该将得到的结果放入队头，不应该是从队尾插入。所以，我们需要使用双端队列，在 C++ 中可以使用 deque 容器。不熟悉的读者可以去做一下B3656。

思路分析

按照广搜的思路，我们每次将第一种移动方式插入队头，将第二种移动方式插入队尾，其余不变。

代码展示

附上 AC 代码：

#include<iostream>
#include<deque>
#include<cstring>
using namespace std;
int n, m, sc, sr, ec, er;
char a[1005][1005];
int vis[1005][1005];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
struct node {
    int x, y, tim;
};
void bfs() {
    deque<node>d;
    d.clear();
    d.push_front((node) { sc, sr, 0 });
    vis[sc][sr] = 0;
    while (!d.empty()) {
        node q = d.front();
        d.pop_front();
        for (int i = 0; i < 4; i++) {
            int nx = q.x + dir[i][0], ny = q.y + dir[i][1];
            if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && vis[nx][ny] > vis[q.x][q.y] && a[nx][ny] == '.') {
                d.push_front((node) { nx, ny, vis[q.x][q.y] });
                vis[nx][ny] = vis[q.x][q.y];
            }
        }
        for (int i = max(q.x - 2, 1); i <= min(q.x + 2, n); i++) {
            for (int j = max(q.y - 2, 1); j <= min(q.y + 2, m); j++) {
                if (vis[i][j] > vis[q.x][q.y] + 1 && a[i][j] == '.') {
                    d.push_back((node) { i, j, vis[q.x][q.y] + 1 });
                    vis[i][j] = vis[q.x][q.y] + 1;
                }
            }
        }
    }
}
int main() {
    cin >> n >> m >> sc >> sr >> ec >> er;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    memset(vis, 0x3f, sizeof(vis));
    bfs();
    if (vis[ec][er] == 0x3f3f3f3f)cout << "-1\n";
    else cout << vis[ec][er] << "\n";
    return 0;
}