学院评估 网站建设整改,网站系统管理,汕头企业建站,企业网站界面 优帮云目录
一、题目
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、思路分析…目录
一、题目
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.husing 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 1000000007;void solve() {int n, m;std::cin n m;std::vectorstd::string g(n);for (int i 0; i n; i)std::cin g[i];int t n m - 1;std::string ans;std::queueint q;q.push(0);std::vectorint vis(n * m);vis[0] true;constexpr int dir[3]{1, 0, 1};while (t --) {ans g[q.front() / m][q.front() % m];std::vectorint 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;
}
