当前位置：首页 > news >正文

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

news 2025/8/15 5:49:40

本文涉及知识点

C++BFS算法

P9065 [yLOI2023] 云梦谣

题目背景

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

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

题目描述

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

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

云梦庭可以看作一个 $n$ 行 $m$ 列的方格阵，第 $i$ 行第 $j$ 列的格子被记作 $(i, j)$ 。每个格子 $(i, j)$ 要么有一个高度 $h_{i,j}$ （ $h_{i,j}$ 为正整数），要么是障碍物，不能通过。（方便起见，约定障碍物的 $h_{i,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}$ 改变为任一正整数。

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

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

输入输出样例 #3

输入 #3

2 5 0
1 0 3 3 4
2 3 4 0 5

输出 #3

输入输出样例 #4

输入 #4

输出 #4

说明/提示

样例 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)$ ，追上了枸杞。

数据规模与约定

对全部的测试点，保证 $\leq n, m \leq 3 \times 10^3$ ， $\leq k,h_{i,j} \leq n \times 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 <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>#include <bitset>
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 _DEBUG		printf("R=%d,C=%d", R,C);Out(mat, ",mat=");Out(rc, ",rc=");//Out(B, "B=");//Out(que, "que=");//Out(B, "B=");
#endif // DEBUG	auto 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);}

扩展阅读

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