読者です 読者をやめる 読者になる 読者になる

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;
  }

}