TopCoder SRM 505 Div1 Easy: RectangleArea
問題
ある大きさの長方形を水平方向に切って N 行に分割する。この時、各行の高さは必ずしも同じではない。次に垂直方向に切って M 列に分割する、この時、各列の幅は必ずしも同じではない。この操作によって、N 行 M 列の小さい長方形の集合になる。
元の長方形の辺の長さや、各長方形の辺の長さは分からないが、一部の長方形の面積は分かっている。元の長方形の面積を知るためには、あといくつの長方形の面積が分かれば良いか。
解法
i 行 j 列目の小さい長方形の面積を map[i][j] とする。
map[r][j] と map[i][c] と map[r][c] が分かれば、map[i][j] が分かる。これを再帰的に行って行けば良い。
コード
public class RectangleArea { boolean[][] map; int H, W; void dfs(int r, int c) { for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (i == r || j == c) continue; int cnt = 0; if (map[i][j]) cnt++; if (map[i][c]) cnt++; if (map[r][j]) cnt++; if (map[r][c]) cnt++; if (cnt == 3) { if (!map[i][j]) { map[i][j] = true; dfs(i, j); } if (!map[i][c]) { map[i][c] = true; dfs(i, c); } if (!map[r][j]) { map[r][j] = true; dfs(r, j); } if (!map[r][c]) { map[r][c] = true; dfs(r, c); } } } } } public int minimumQueries(String[] known) { H = known.length; W = known[0].length(); map = new boolean[H][W]; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { map[i][j] = known[i].charAt(j) == 'Y'; } } for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { dfs(i, j); } } int ans = 0; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (map[i][j]) continue; map[i][j] = true; ans++; dfs(i, j); } } return ans; } }