ARC 031 B - 埋め立て
問題概要
盤面上での陸地の繋がりを調べえる問題。ただし、1マス分だけ陸地にすることができる。
解法
10x10の盤面で小さいので、100個あるマスを1つ変えた時に、どうなるかを調べる。全探索するということ。 回りの4方向で陸どおしでつながっている部分をUnion Find構造で管理して、最後に、陸の部分でいくつのグループができているかをsetで管理して、その値が1であれば陸の中でグループが1つしかできていないのだから、YESということになる。Union findで管理するものはよく頂点番号で当たられているが、今回のような盤面の問題であっても、番目の左上から右下へ番号を振り、それを頂点番号としてあつかえば同様なことができる。
ミス
classでunion find構造を作っていなくて、同じ配列を使いまわしていて、1WA。
コード
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <cstdio> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int MAX_N = 110; //Quick Find Weighted class QuickFindWeighted{ public: int i2g[MAX_N];//i2g[i] := 頂点iが所属するグループ vector<int> g2i[MAX_N];//g2i[g]:= グループgに所属する頂点番号 void init(int n){ for (int i = 0; i < n; ++i){ i2g[i] = i; g2i[i].push_back(i); } } // 座標iaと座標ibは同じグループに所属しているか? bool issame(int ia, int ib){ return i2g[ia] == i2g[ib]; } // 座標iaの所属するグループと座標ibの所属するグループを1つにする(異なるグループに属するものに) void merge(int ia, int ib){ if(issame(ia, ib)) return; //iaの所属するグループがibの所属するグループより小さくならないようにする(一般的マージテク) if(g2i[i2g[ia]].size() < g2i[i2g[ib]].size()){ swap(ia, ib); } int ga = i2g[ia], gb = i2g[ib];//グループgbの方が要素数が少ない for(auto u : g2i[gb]){//uには頂点の番号はいる i2g[u] = ga;//グループの番号を更新 } g2i[ga].insert(g2i[ga].end(), g2i[gb].begin(), g2i[gb].end());//つなげる g2i[gb].clear(); } }; string a[10]; int dy[] = {1, 0, -1, 0}; int dx[] = {0, 1, 0, -1}; bool flag = false; int main(void){ rep(i, 10) cin >> a[i]; rep(i, 10)rep(j, 10){ char t = a[i][j]; a[i][j] = 'o'; QuickFindWeighted uf; uf.init(100); rep(y, 10)rep(x, 10){//つながっている部分を同じグループにする if(a[y][x] == 'x') continue; rep(k, 4){ int ny = y + dy[k], nx = x + dx[k]; if(!(0 <= ny && ny < 10 && 0 <= nx && nx < 10)) continue; if(a[ny][nx] == 'x') continue; uf.merge(y * 10 + x, ny * 10 + nx); } } //陸地のグループ数を数える set<int> s; rep(y, 10)rep(x, 10){ if(a[y][x] == 'o'){ s.insert(uf.i2g[y * 10 + x]); } } if(s.size() == 1) flag = true; a[i][j] = t; } if(flag) printf("YES\n"); else printf("NO\n"); return 0; }