铺瓷砖

Posted on In Views: Waline: Views: Symbols count in article: 683 Reading time ≈ 1 mins.

题解方法

  • 深度优先搜索

深度优先搜索

  1. Do 访问 (x, y)：
    1. If 抵达右边界，换行，结束。
    2. If 抵达下边界，保存当前瓷砖数为最小瓷砖数，结束。
    3. If filled，访问 (x, y + 1)。
    4. If 当前当前瓷砖数 + 1 > 最小瓷砖数，说明该方案不是最优解，结束。
    5. Do 选择填充正方形，边长 $len \in [1, \min(n - x, m - y)]$：
      1. If 已填充，break。
      2. 填充正方形。
      3. 访问 (x, y + len)。
      4. 取消填充。

核心代码

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private void dfs(int x, int y, int cnt) {
	// 抵达右边界，换行
	if (y == m) {
		dfs(x + 1, 0, cnt);
		return;
	}
	// 抵达下边界，结束
	if (x == n) {
		minCnt = cnt;
		return;
	}
	if (filled[x][y]) {
		dfs(x, y + 1, cnt);
	}
	// 如果继续填充，则超过当前最小值，结束
	if (++cnt >= minCnt) {
		return;
	}
	int maxLen = Math.min(n - x, m - y);
	for (int i = 1; i <= maxLen; i++) {
		if (isFilled(x, y, i)) {
			break;
		}
		fill(x, y, i);
		dfs(x, y + i, cnt);
		unFill(x, y, i);
	}
}

题目来源