SRM505 Div1 Easy - RectangleArea
問題
H*Wの長方形をN*M個に区切り、そのうちいくつかの部分の面積を知っている
全体の面積を知りたいとき追加で必要な区間の面積の情報の最小値を求める
解法
Rx*Cx, Rx*Cy, Ry*Cx, Ry*Cyのうち3つの面積がわかれば残り1つの面積がわかる
これを利用して盤面を埋めていく
実装
まずは全探索して初期状態のNのうち↑の条件から実はYなものをYに書き換えておく
それでもNのままのマスは絶対に追加情報が必要だから答えを+1してそこをYに変え、それをきっかけにYに変わるマスを再帰で書き換える
class RectangleArea { public: vector<string> s; int h, w, res; void rec(int r, int c) { rep(i,h) rep(j,w) if (i!=r && j!=c) { int t = (s[i][j]=='Y') + (s[i][c]=='Y') + (s[r][j]=='Y'); if (t!=2) continue; if (s[i][j]=='N') s[i][j] = 'Y', rec(i,j); else if (s[i][c]=='N') s[i][c] = 'Y', rec(i,c); else s[r][j] = 'Y', rec(r,j); } } int minimumQueries(vector<string> ss) { s = ss, h = s.size(), w = s[0].size(); rep(i,h) rep(j,w) if (s[i][j]=='Y') rec(i,j); rep(i,h) rep(j,w) if (s[i][j]=='N') s[i][j] = 'Y', rec(i,j), res++; return res; } };