【BFS】P9065 [yLOI2023] 云梦谣|普及+

本文涉及知识点

C++BFS算法

P9065 [yLOI2023] 云梦谣

题目背景

归来且做云梦梦一场 大梦好
栽花闻酒香 醒醒醉醉笑笑
天地偌大复路远山高 最难得偷半日逍遥
偶尔糊涂不问世事不知晓

——银临 & 慕寒《云梦谣》

题目描述

“喂，枸杞，你这只笨狗，又偷吃！看我不收拾你！”

朵一气呼呼地从院子里跑出来，手中握着掸子，而枸杞早已不见踪影。

云梦庭可以看作一个 $n$ 行 $m$ 列的方格阵，第 $i$ 行第 $j$ 列的格子被记作 $(i,j)$。每个格子 $(i,j)$ 要么有一个高度 h i , j h_{i,j} hi,j​（ h i , j h_{i,j} hi,j​ 为正整数），要么是障碍物，不能通过。（方便起见，约定障碍物的 h i , j h_{i,j} hi,j​ 用 $0$ 表示。）另外，云梦庭上有 $k$ 个指定的格子上可以进行御剑飞行。开始时，朵一和枸杞分别位于方格 $(1,1)$ 和 $(n,m)$。

朵一的御剑飞行还不是很熟练，现在她还控制不好御剑的高度。因此在任意时刻，朵一在方格 $(i,j)$ 上可以做如下行动之一：

• 移动到与该方格相邻的方格 $(i-1,j)$、$(i+1,j)$、$(i,j-1)$、$(i,j+1)$ 之一上（不能移动出方格边界，也不能移动到障碍物上）；
• 如果方格 $(i,j)$ 上允许御剑飞行，则朵一可以御剑飞行至另一个同样允许御剑飞行且与方格 $(i,j)$ 高度相等的方格上；
• 使用仙法将当前格子的高度 h i , j h_{i,j} hi,j​ 改变为任一正整数。

进行上述每项行动均需花费 $1$ 个单位时间。

“哼，笨狗子你再跑！”说罢，朵一便追了出去。朵一接下来还要尽快继续今天的修行，因此她想知道到达 $(n,m)$ 格子所需的最短时间是多少。

输入格式

输入的第一行有三个整数，依次表示方格阵的行数 $n$、列数 $m$ 和能御剑飞行的方格个数 $k$。
接下来 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数表示方格 $(i,j)$ 的高度 h i , j h_{i,j} hi,j​。数据保证 h 1 , 1 h_{1,1} h1,1​ 和 h n , m h_{n,m} hn,m​ 不为 $0$。
接下来 $k$ 行，每行两个整数 $x$ 和 $y$，表示一个允许御剑飞行的方格的坐标 $(x,y)$。数据保证这 $k$ 个方格的坐标互不相同。

输出格式

一行一个整数，表示朵一到达 $(n,m)$ 所需的最小时间。如果朵一无法到达，输出 -1。

输入输出样例 #1

输入 #1

4 4 21 2 3 41 2 3 41 2 3 41 2 3 41 13 4

输出 #1

3

输入输出样例 #2

输入 #2

4 4 31 2 3 41 2 3 41 2 3 41 2 3 41 12 44 1

输出 #2

4

输入输出样例 #3

输入 #3

2 5 01 0 3 3 42 3 4 0 5

输出 #3

7

输入输出样例 #4

输入 #4

4 4 31 1 1 01 1 0 11 0 1 10 1 1 11 12 13 3

输出 #4

3

说明/提示

样例 1 解释

第 $1$ 个单位时间，朵一将当前方格 $(1,1)$ 的高度修改为 $4$；
第 $2$ 个单位时间，朵一从方格 $(1,1)$ 御剑飞行至 $(3,4)$；
第 $3$ 个单位时间，朵一从方格 $(3,4)$ 移动到 $(4,4)$，追上了枸杞。

样例 2 解释

第 $1$ 个单位时间，朵一从方格 $(1,1)$ 御剑飞行至 $(4,1)$；
第 $2$ 个单位时间，朵一从方格 $(4,1)$ 移动到 $(4,2)$；
第 $3$ 个单位时间，朵一从方格 $(4,2)$ 移动到 $(4,3)$；
第 $4$ 个单位时间，朵一从方格 $(4,3)$ 移动到 $(4,4)$，追上了枸杞。

数据规模与约定

对全部的测试点，保证 1≤n,m≤3× 10 3 1 \\leq n, m \\leq 3 \\times 10^3 1≤n,m≤3×103， 0≤k, h i , j ≤n×m 0 \\leq k,h_{i,j} \\leq n \\times m 0≤k,hi,j​≤n×m。

提示

请注意大量数据读入对程序效率造成的影响，选择合适的读入方式，避免超时。

说明

本题共有 5 个附加样例文件，见附件里的 dream.zip。

后记

不过，别看朵一现在一副生气的样子，可当她追上枸杞后，大抵是不舍得真的动手吧。“嘿嘿，今日的修行结束后，该吃什么好呢？”在这飞瀑悬挂、翠竹怀抱的云梦庭中，修仙炼体，不羡尘嚣，应是这世上最逍遥的事了。

BFS

**性质一 * *：存在最优解，飞行次数不超过1。如果飞行次数大于1，第一次飞行的起点是u，最后一次飞行的终点是v，则直接从u飞行到v是不劣解。
性质二：令飞行一次的最优解从u飞行到v。则不存在可飞行点到起点的距离小于u，到终点的距离小于v。
两次BFS，BFS起点分别是本题起点和终点。令起点到任意飞行点最短的距离是d1，v1记录所有到起点距离为d1的高度。令终点到任意飞行点的最短距离是d2，v2
记录所有到终点距离d2的飞行点高度。如果v2和v1有交集，则一次飞行的最短距离是：d1+d2+1，否则是d1+d2+2。如果v1或v2为空，则无法飞行。
0次飞行是dis1.back()。
时间复杂度：O(nm)

代码

核心代码

#include #include #include #include#include#include#include#include#include#include#include#include #include#include#include #include #include#include#include#include#include using namespace std;template<class T1, class T2>std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;}template<class T1, class T2, class T3 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;}template<class T1, class T2, class T3, class T4 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;}template<class T = int>vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;}template<class T = int>vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if (\'\\n\' == cin.get()) { break; }}return ret;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;}template<int N = 1\'000\'000>class COutBuff{public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = \'-\', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char puffer[N], * m_p;};template<int N = 1\'000\'000>class CInBuff{public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();while ((\'\\r\' == *S) || (\'\\n\' == *S) || (\' \' == *S)) { S++; }//忽略空格和回车ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == \'-\');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == \'-\');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;};class CGrid {public:CGrid(int rCount, int cCount) :m_r(rCount), m_c(cCount) {}template<class Fun1, class Fun2>vector<vector<pair<int, int>>> NeiBo(Fun1 funVilidCur, Fun2 funVilidNext, int iConnect = 4){vector<vector<pair<int, int>>> vNeiBo(m_r * m_c);for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){if (!funVilidCur(r, c))continue;auto& v = vNeiBo[Mask(r, c)];if ((r > 0) && funVilidNext(r - 1, c)) {v.emplace_back(r - 1, c);}if ((c > 0) && funVilidNext(r, c - 1)) {v.emplace_back(r, c - 1);}if ((r + 1 < m_r) && funVilidNext(r + 1, c)) {v.emplace_back(r + 1, c);}if ((c + 1 < m_c) && funVilidNext(r, c + 1)) {v.emplace_back(r, c + 1);}}}return vNeiBo;}vector<vector<int>> Dis(vector<pair<int, int>> start, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, const int& iConnect = 4) {static short dir[8][2] = { {0, 1}, {1, 0}, {-1, 0},{ 0, -1},{1,1},{1,-1},{-1,1},{-1,-1} };vector<vector<int>> vDis(m_r, vector<int>(m_c, -1));for (const auto& [r, c] : start) {vDis[r][c] = 0;}for (int i = 0; i < start.size(); i++) {const auto [r, c] = start[i];if (!funVilidCur(r, c)) { continue; }for (int k = 0; k < iConnect; k++) {const int r1 = r + dir[k][0];const int c1 = c + dir[k][1];if ((r1 < 0) || (r1 >= m_r) || (c1 < 0) || (c1 >= m_c)) { continue; }if (funVilidNext(r1, c1) && (-1 == vDis[r1][c1])) {start.emplace_back(r1, c1);vDis[r1][c1] = vDis[r][c] + 1;}}}return vDis;}void EnumGrid(std::function<void(int, int)> call){for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){call(r, c);}}}vector<pair<int, int>> GetPos(std::function<bool(int, int)> fun) {vector<pair<int, int>> ret;for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){if (fun(r, c)) {ret.emplace_back(r, c);}}}return ret;}inline int Mask(int r, int c) { return m_c * r + c; }const int m_r, m_c;const inline static int s_Moves[][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };};class Solution {public:int Ans(const int R, const int C, vector<vector<int>>& mat, vector<pair<int, int>>& rc) {CGrid grid(R, C);auto Vilid = [&](int r, int c) {return 0 != mat[r][c]; };auto dis0 = grid.Dis({ {0,0} }, Vilid, Vilid);auto dis1 = grid.Dis({ {R - 1,C - 1} }, Vilid, Vilid);int iM1 = INT_MAX / 2, iM0 = INT_MAX / 2;for (auto& [r, c] : rc) {r--; c--;if (-1 != dis0[r][c]){iM0 = min(iM0, dis0[r][c]);}if (-1 != dis1[r][c]){iM1 = min(iM1, dis1[r][c]);}}int ans = (-1 == dis1[0][0]) ? INT_MAX / 2 : dis1[0][0];if ((-1 == dis1[0][0]) && (INT_MAX / 2 == max(iM0, iM1))) { return -1; }if (INT_MAX / 2 == max(iM0, iM1)) { return dis1[0][0]; }vector<int> has(R * C + 1);for (const auto& [r, c] : rc) {if (iM0 == dis0[r][c]) {has[mat[r][c]] |= 1;}if (iM1 == dis1[r][c]) {has[mat[r][c]] |= 2;}}for (int i = 1; i <= R * C; i++) {if (3 == has[i]) { return min(ans, iM0 + iM1 + 1); };}return min(ans, iM0 + iM1 + 2);};};int main() {#ifdef _DEBUGfreopen(\"a.in\", \"r\", stdin);#endif // DEBUG//ios::sync_with_stdio(0); cin.tie(nullptr);CInBuff<> in; COutBuff<10\'000\'000> ob;int R, C, Q;in >> R >> C >> Q;vector<vector<int>> mat(R);for (int r = 0; r < R; r++) {mat[r] = in.Read<int>(C);}auto rc = in.Read<pair<int,int>>(Q);#ifdef _DEBUGprintf(\"R=%d,C=%d\", R,C);Out(mat, \",mat=\");Out(rc, \",rc=\");//Out(B, \"B=\");//Out(que, \"que=\");//Out(B, \"B=\");#endif // DEBUGauto res = Solution().Ans(R,C,mat,rc);cout << res;return 0;}

单元测试

int R, C;vector<vector<int>> mat;vector<pair<int, int>> rc;TEST_METHOD(TestMethod1){R = 4, C = 4, mat = { {1,2,3,4},{1,2,3,4},{1,2,3,4},{1,2,3,4} }, rc = { {1,1},{3,4} };auto res = Solution().Ans(R,C,mat,rc);AssertEx(3, res);}TEST_METHOD(TestMethod2){R = 4, C = 4, mat = { {1,0,1,1},{1,0,1,1},{1,1,1,1},{0,0,0,1} }, rc = {};auto res = Solution().Ans(R, C, mat, rc);AssertEx(6, res);}

扩展阅读

我想对大家说的话 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 如果程序是一条龙，那算法就是他的是睛 失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。