BFS

ABC142F 解法 Sub 0: 有向グラフにおける，サイクルを求める． Sub 1: 有向グラフにおける，最短サイクルを求める． Sub 0: サイクルを検出するだけなら，DFS, BFS で可能． Sub 1: 最短のサイクルを求めたいので，BFS を行う． 計算量的には，始点 \(i \in N\) を全探索して BFS をしても間に合う． よって，\(i\) を始点とする BFS をして， サイクル \(i \rightarrow i\) を求める． BFS の途中でサイクルを検出するかもしれないが無視する． 使っている記号，マクロ等 "https://ecsmtlir.hatena…

ABC317E 実装が少し面倒だが，ただの BFS. 前処理として，通れないマス全体を求めておくと楽． それさえ出来ていれば，グリッドに対する BFS をするだけ． 実装例: 公式解説の方法を載せる． 通れない頂点は，BFS で既に調べた頂点として初期化しておけばよい． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll h,w ; cin >> h >> w; vector<string> a(h); cinv(a); vector<char> v = {'>', 'v'…

\( \def \ra {\rightarrow} \) ABC257F テレポータの行き先を超頂点 \(X \not\in N\) とおく． \(X\) を頂点として加えたグラフを考える． これにより，テレポータの行き先を保留した状態でグラフを構成できる． \(X\) の行き先を \(i\) としたいときは， コスト 0 の辺 \(i \rightarrow X\) を追加すればよい． すでにコスト 1の辺 \(i \rightarrow X\) があるかもしれないが， 最短経路を計算するときはコスト 0 の方が採用されるので，無駄な辺が残っていても問題ない． 各 \(i \in N \) …

ABC241F 大事な座標だけもって BFS. オブジェクトの周囲 4マスだけがグラフの頂点となる． map や upper_bound を使うので，遷移ごとに \(log(V)\) がかかる． ここで \(V\) は vertex の集合のサイズ． 前処理にもソートで \(log V\) が余分にかかる． 遷移しながらグラフを構成してる感じであって，前もってグラフを作る必要はない． 実装遷移するとき，高速に障害物の位置を取得すれば十分． 今いる座標と同じ行(または列)に障害物があるか，あるならその直前の座標を取得したい． これは，\(x\) 座標に対して，障害物が座標 \( (x,y) \)…

ABC197F 問題文で与えられたグラフを \(G\) とおく． 解法1: BFS 素直な実装． 頂点が \(N \times N\) のグラフ \(\hat{G}\) を考える． \(\hat{G}\) における 頂点 \(\,(x,y), (nx,ny)\,\) に対する辺は， \(G\) において辺 \(e = (x,y,c), ne = (nx,ny,nc)\) が存在して \(c = nc\) のときに張る． ここで，\(e\)は \(x\) から \(y\) への辺であって，文字 \(c\) が割り当てられているものを表す． \(\hat{G}\) における遷移は， 回文を外側から…

ABC190E グラフの問題． ハミルトン閉路に近い． 大事な頂点が \(K \leq 17\) と少ない． 訪れた頂点を再び使う可能性はある． すべての大事な頂点を 1回以上使う． 訪れた頂点の集合と，最後に訪れた頂点を保持しながら dp. 大事な頂点間のコストは，BFS とWarshall-Floyd で求めておく． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, m; cin >> n >> m; vvll to(n); rep(i,m){ ll a,b; …

ABC311 D BFS で求まる． 訪れたマスを記録しておいて，1回しか調べないことにする． ただし，通過したマスと止まったマスは区別する． 遷移するとき，ぶつかるまで一気に進むので while 文で実装する． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { vll n(2); cinv(n); vector<string> s(n[0]); cinv(s); queue<vll> q; vvvll vis(n[0], vvll(n[1], vll(2))); q.push…