1
class Solution {
2
  int ret; // store the final result
3
  int m, n; // m is the height, and n is the width
4

5
  // Note: original signature is changed from n,m to m,n
6
  public int tilingRectangle(int m, int n) {
7
    this.m = m;
8
    this.n = n;
9
    this.ret = m * n; // initilize the result as m*n if cut rectangle to be all 1*1 squares
10
    int[][] mat =
11
        new int[m][n]; // record the status of every location, 0 means not covered, 1 means covered
12
    backtrack(mat, 0); // start backtracking
13
    return ret;
14
  }
15

16
  // the size means how many squares cut now
17
  public void backtrack(int[][] mat, int size) {
18
    if (size > ret)
19
      return; // if we already have more squares than the min result, no need to go forward
20

21
    // find out the leftmost and topmost postion where is not covered yet
22
    int x = -1, y = -1;
23
    for (int i = 0; i < m; i++) {
24
      for (int j = 0; j < n; j++) {
25
        if (mat[i][j] == 0) {
26
          x = i;
27
          y = j;
28
          break;
29
        }
30
      }
31
      if (x != -1 && y != -1) break;
32
    }
33
    // if not found, we know that all positions are covered
34
    if (x == -1 && y == -1) {
35
      // update the result
36
      ret = Math.min(size, ret);
37
    } else {
38
      int len = findWidth(x, y, mat); // find the maximum width to cut the square
39
      while (len >= 1) {
40
        cover(x, y, len, mat, 1); // cover the current square
41
        backtrack(mat, size + 1);
42
        cover(x, y, len, mat, 0); // uncover the previous result
43
        len--; // decrement the square width by 1
44
      }
45
    }
46
  }
47

48
  public int findWidth(int x, int y, int[][] mat) {
49
    int len = 1;
50
    while (x + len < m && y + len < n) {
51
      boolean flag = true; // flag means the len is reachable
52
      for (int i = 0; i <= len; i++) {
53
        // check the right i-th column and the bottom i-th row away from (x, y)
54
        if (mat[x + i][y + len] == 1 || mat[x + len][y + i] == 1) {
55
          flag = false;
56
          break;
57
        }
58
      }
59
      if (!flag) break;
60
      len++;
61
    }
62
    return len;
63
  }
64

65
  public void cover(int x, int y, int len, int[][] mat, int val) {
66
    for (int i = x; i < x + len; i++) {
67
      for (int j = y; j < y + len; j++) {
68
        mat[i][j] = val;
69
      }
70
    }
71
  }
72
}