盘锦网站建设兼职,ppt设计多少钱一页,w3school网站建设教程,品牌咨询公司一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
https://codeforces.com/problemset/problem/196/B 二、解题报告
1、思路分析
考虑如何判断一条路径可以无限走#xff1f;
我们对朴素的网格dfs改进#xff0c;改进为可以dfs网格外的区域
如果存在某个…一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
https://codeforces.com/problemset/problem/196/B 二、解题报告
1、思路分析
考虑如何判断一条路径可以无限走
我们对朴素的网格dfs改进改进为可以dfs网格外的区域
如果存在某个 位置 (i % n, j % m) 被访问两次并且两次的(i, j)不同则说明进入了一条路径的循环合法。
2、复杂度 时间复杂度 O(NM)空间复杂度O(NM) 3、代码详解
#include bits/stdc.h
// #include ranges
// #define DEBUG
using i64 long long;
using u32 unsigned;
using u64 unsigned long long;
constexpr int inf32 1E9 7;
constexpr i64 inf64 1E18 7;
constexpr double eps 1e-9;struct DSU {std::vectorint p;int n;DSU(int _n) : p(_n, -1), n(_n) {}void init () {p.assign(n, -1);}int find(int x) {return p[x] 0 ? x : p[x] find(p[x]);}void merge(int x, int y) {int px find(x), py find(y);if (px py) return;if (p[px] p[py]) std::swap(px, py);p[px] p[py], p[py] px;}int size(int x) {return -p[find(x)];}
};constexpr int dir[5] { -1, 0, 1, 0, -1 };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];if (n 1 m 1) {std::cout Yes;return;}int stx, sty;for (int i 0; i n; i)for (int j 0; j m; j) if (g[i][j] S) {stx i, sty j;break;}auto pos [m](int i, int j) {return i * m j;};std::vectorstd::pairint, int st, vis(n * m, { inf32, inf32 });st.emplace_back(stx, sty);vis[pos(stx, sty)] { stx, sty };while (st.size()) {auto [x, y] st.back();st.pop_back();for (int k 0; k 4; k) {auto [nx, ny] std::pair(x dir[k], y dir[k 1]);auto [nnx, nny] std::pair(((nx % n) n) % n, ((ny % m) m) % m);// assert(nnx 0 nnx n);// assert(nny 0 nny m);if (g[nnx][nny] ! #) {if (vis[pos(nnx, nny)].first inf32) {if(vis[pos(nnx, nny)] ! std::pair(nx, ny)) {std::cout Yes;return;}}else {vis[pos(nnx, nny)] { nx, ny };st.emplace_back(nx, ny);}}}}std::cout No;
}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);#endif int t 1;// std::cin t;while (t --)solve();return 0;
}
