贪心 + 分层图bfs，newcoder 76652/B

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

https://ac.nowcoder.com/acm/contest/76652/B

---

二、解题报告

1、思路分析

以(0, 0) 为起点，进行bfs

bfs可以每次扩展一层，我们每次选择可扩展位置中字符最小的那些

这样我们会进行多路增广

由于路径长度为n + m - 1，所以只需增广 n + m - 1 次

2、复杂度

时间复杂度： O(NMlogNM)空间复杂度：O(NM)

3、代码详解

 ​

#include <bits/stdc++.h>using i64 = long long;
using i32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 1'000'000'007;void solve() {int n, m;std::cin >> n >> m;std::vector<std::string> g(n);for (int i = 0; i < n; ++ i)std::cin >> g[i];int t = n + m - 1;std::string ans;std::queue<int> q;q.push(0);std::vector<int> vis(n * m);vis[0] = true;constexpr int dir[3]{1, 0, 1};while (t --) {ans += g[q.front() / m][q.front() % m];std::vector<int> buf;while(q.size()) {int i = q.front();q.pop();int x = i / m, y = i % m;for (int k = 0; k < 2; ++ k) {int nx = dir[k] + x, ny = dir[k + 1] + y;if (nx < 0 || ny < 0 || nx >= n || ny >= m || vis[nx * m + ny]) continue;buf.push_back(nx * m + ny);vis[nx * m + ny] = true;}}std::sort(buf.begin(), buf.end(), [&](int i, int j) -> bool{return g[i / m][i % m] < g[j / m][j % m];});for (int i = 0; i < buf.size() && g[buf[0] / m][buf[0] % m] == g[buf[i] / m][buf[i] % m]; ++ i)q.push(buf[i]);}std::cout << ans;
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
}();int main () {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifint T = 1;// std::cin >> T;while (T --)solve();return 0;
}