2020-03-01 23:08:51
問題描述:
你有一塊棋盤,棋盤上有一些格子已經壞掉了。你還有無窮塊大小為1 * 2的多米諾骨牌,你想把這些骨牌不重疊地覆寫在完好的格子上,請找出你最多能在棋盤上放多少塊骨牌?這些骨牌可以橫着或者豎着放。
輸入:n, m代表棋盤的大小;broken是一個b * 2的二維數組,其中每個元素代表棋盤上每一個壞掉的格子的位置。
輸出:一個整數,代表最多能在棋盤上放的骨牌數。
示例 1:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5yM5IGNhNGZygTOilTNiZTZyATYzIjZ2QmYwgjZxkTN08CX0EzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjL2M3Lc9CX6MHc0RHaiojIsJye.png)
輸入:n = 2, m = 3, broken = [[1, 0], [1, 1]]
輸出:2
解釋:我們最多可以放兩塊骨牌:[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。
示例 2:
輸入:n = 3, m = 3, broken = []
輸出:4
解釋:下圖是其中一種可行的擺放方式
限制:
1 <= n <= 8
1 <= m <= 8
0 <= b <= n * m
問題求解:
public int domino(int m, int n, int[][] broken) {
int[][] dp = new int[m + 1][1 << n];
int[][] board = new int[m][n];
for (int[] b : broken) board[b[0]][b[1]] = 1;
int[] states = new int[m + 1];
states[0] = (1 << n) - 1;
for (int i = 1; i <= m; i++) {
int state = 0;
for (int j = 0; j < n; j++) {
if (board[i - 1][j] == 1) state |= (1 << (n - 1 - j));
}
states[i] = state;
}
for (int i = 1; i <= m; i++) {
for (int u = 0; u < 1 << n; u++) {
if ((u & states[i - 1]) != 0) continue;
int prev = u | states[i - 1];
for (int v = 0; v < 1 << n; v++) {
if ((v & states[i]) != 0) continue;
// 枚舉豎放的位置
for (int k = v;; k = (k - 1) & v) {
if ((k & prev) == 0) {
dp[i][v] = Math.max(dp[i][v], calc_1(k) + calc_2(v ^ k) + dp[i - 1][u]);
}
if (k == 0) break;
}
}
}
}
int res = 0;
for (int i = 0; i < 1 << n; i++) res = Math.max(res, dp[m][i]);
return res;
}
private int calc_1(int num) {
int res = 0;
for (int i = 0; i < 32; i++) if ((num & (1 << i)) != 0) res += 1;
return res;
}
private int calc_2(int num) {
int res = 0;
for (int i = 0; i < 32;) {
if ((num & (1 << i)) != 0 && i + 1 < 32 && (num & (1 << (i + 1))) != 0) {
res += 1;
i += 2;
}
else {
i += 1;
}
}
return res;
}