[AtCoder] AISing Programming Contest 2019 C – Alternating Path
問題
方針
各マスに番号を割り振る
\( H \) 行 \( W \) 列のマスを持つグリッドにおける \( i \) 行 \( j \) 列目のマスの番号を \( i \times W + j \) とします。このようにマスの番号を割り当てると \( 0 \) から \( HW – 1 \) までの範囲で一意に番号を持ちます。
パスの数を求める (深さ優先探索)
黒マスから白マスへのパスの数の合計を求めます。ただし、パスは黒白黒白黒…と交互に色が変わるパスとします。
ある黒マス \( B_i(x_i, y_i)\) を始点として、到達できる白マスと黒マスの数 \( w_i, b_i \) を求めます。このとき、始点の黒マスもカウントします。到達できるマスは全て連結されているので、任意の黒マスから任意の白マスへのパスが存在します。したがって、この連結において求めるパスの合計は \( w_ib_i \) となります。
パスの数を求める (Union Find)
ある要素がどのグループに属すかといった問題では、Union Find を使うことができます。Union Find については、下の記事がまとまっていると思います。
あるパスにおける白マスと黒マスの個数が分かればよいでの、Union Find を使ってそれらを求めます。
コード
提出したコード (深さ優先探索)
提出したコード (Union Find)
Union Find
class DisjointSet { public: vector<int> p, rank, size; DisjointSet(int n) { p.assign(n, 0); rank.assign(n, 0); size.assign(n, 0); for (int i = 0; i < n; i++) { make_set(i); } } void make_set(int x) { p[x] = x; rank[x] = 0; size[x] = 1; } int find_set(int x) { if (x != p[x]) { p[x] = find_set(p[x]); } return p[x]; } bool same(int x, int y) { return find_set(x) == find_set(y);; } int union_size(int x) { if (x != p[x]) { size[x] = union_size(find_set(x)); } return size[x]; } void link(int x, int y) { if(rank[x] > rank[y]) { p[y] = x; size[x] = size[x] + size[y]; }else if(rank[x] < rank[y]){ p[x] = y; size[y] = size[x] + size[y]; }else if(x != y) { p[y] = x; rank[x]++; size[x] = size[x] + size[y]; } } void unite(int x, int y) { link(find_set(x), find_set(y)); } };
ディスカッション
コメント一覧
まだ、コメントがありません