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

本文涉及知识点

C++BFS算法

P9065 [yLOI2023] 云梦谣

题目背景

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

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

题目描述

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

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

云梦庭可以看作一个

$n$ 行

$m$ 列的方格阵，第

$i$ 行第

$j$ 列的格子被记作

(

)

(i,j)

$(i, j)$ 。每个格子

(

)

(i,j)

$(i, j)$ 要么有一个高度

h_{i,j}

$h_{i, j}$ （

h_{i,j}

$h_{i, j}$ 为正整数），要么是障碍物，不能通过。（方便起见，约定障碍物的

h_{i,j}

$h_{i, j}$ 用

$0$ 表示。）另外，云梦庭上有

$k$ 个指定的格子上可以进行御剑飞行。开始时，朵一和枸杞分别位于方格

(

)

(1,1)

$(1, 1)$ 和

(

)

(n,m)

$(n, m)$ 。

朵一的御剑飞行还不是很熟练，现在她还控制不好御剑的高度。因此在任意时刻，朵一在方格

(

)

(i,j)

$(i, j)$ 上可以做如下行动之一：

移动到与该方格相邻的方格
如果方格
使用仙法将当前格子的高度 $h_{i,j} hi,j 改变为任一正整数。$

进行上述每项行动均需花费

$1$ 个单位时间。

“哼，笨狗子你再跑！”说罢，朵一便追了出去。朵一接下来还要尽快继续今天的修行，因此她想知道到达

(

)

(n,m)

$(n, m)$ 格子所需的最短时间是多少。

输入格式

输入的第一行有三个整数，依次表示方格阵的行数

$n$ 、列数

$m$ 和能御剑飞行的方格个数

$k$ 。接下来

$n$ 行，每行

$m$ 个整数，其中第

$i$ 行的第

$j$ 个数表示方格

(

)

(i,j)

$(i, j)$ 的高度

h_{i,j}

$h_{i, j}$ 。数据保证

h_{1,1}

$h_{1, 1}$ 和

h_{n,m}

$h_{n, m}$ 不为

$0$ 。接下来

$k$ 行，每行两个整数

$x$ 和

$y$ ，表示一个允许御剑飞行的方格的坐标

(

)

(x, y)

$(x, y)$ 。数据保证这

$k$ 个方格的坐标互不相同。

输出格式

一行一个整数，表示朵一到达

(

)

(n,m)

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

输入输出样例 #1

输入 #1

4 4 2
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 1
3 4

输出 #1

输入输出样例 #2

输入 #2

4 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 1
2 4
4 1

输出 #2

输入输出样例 #3

输入 #3

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

输出 #3

输入输出样例 #4

输入 #4

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

输出 #4

说明/提示

样例 1 解释

第

$1$ 个单位时间，朵一将当前方格

(

)

(1,1)

$(1, 1)$ 的高度修改为

$4$ ；第

$2$ 个单位时间，朵一从方格

(

)

(1,1)

$(1, 1)$ 御剑飞行至

(

)

(3,4)

$(3, 4)$ ；第

$3$ 个单位时间，朵一从方格

(

)

(3,4)

$(3, 4)$ 移动到

(

)

(4,4)

$(4, 4)$ ，追上了枸杞。

样例 2 解释

第

$1$ 个单位时间，朵一从方格

(

)

(1,1)

$(1, 1)$ 御剑飞行至

(

)

(4,1)

$(4, 1)$ ；第

$2$ 个单位时间，朵一从方格

(

)

(4,1)

$(4, 1)$ 移动到

(

)

(4,2)

$(4, 2)$ ；第

$3$ 个单位时间，朵一从方格

(

)

(4,2)

$(4, 2)$ 移动到

(

)

(4,3)

$(4, 3)$ ；第

$4$ 个单位时间，朵一从方格

(

)

(4,3)

$(4, 3)$ 移动到

(

)

(4,4)

$(4, 4)$ ，追上了枸杞。

数据规模与约定

对全部的测试点，保证

≤

1 \\leq n, m \\leq 3 \\times 10^3

$1 \leq n, m \leq 3 \times 1 0^{3}$ ，

≤

0 \\leq k,h_{i,j} \\leq n \\times m

$0 \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 _DEBUG
freopen("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);
}

扩展阅读

我想对大家说的话

工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。

学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作

有效学习：明确的目标及时的反馈拉伸区（难度合适）专注

闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。

子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。

如果程序是一条龙，那算法就是他的是睛

失败+反思=成功成功+反思=成功

视频课程

先学简单的课程，请移步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++**实现。

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

本文涉及知识点

P9065 [yLOI2023] 云梦谣

题目背景

题目描述

输入格式