在线评测链接:P1310

题目描述

塔子哥带领着一支拥有激情和创新的团队，决定建设一个全新的园区。他们经过深入调研和思考，最终选择了一块荒地，并开始了紧张而充满挑战的规划和建设工作。在大家的共同奋斗下，新园区建成了，它不仅令人刮目相看的现代化设计，更彰显着这个团队的勇气和实干精神。园区的诞生，也为附近居民和企业带来了无限机遇和福祉。

现在塔子哥打算购买一块 $m$ $\times$ $n$ 大小的土地，用于建设新土地。他希望将这块土地规划为尽可能少的正方形区域。他想起原先这个问题在acm竞赛中非常熟悉，但是由于他已经退役n年了，所以想寻求大家的帮助。

请注意，规划完这块土地以后，应该满足一个状态：没有任何一个正方形能放入！

输入描述

输入第一行为一个整数 $m$ 。

输入第二行为一个整数 $n$ 。

其中1 $\leq$ $m$ $\leq$ $13$ ， $1$ $\leq$ $n$ $\leq$ $13$ .

输出描述

输出为一个整数，表示最少能规划块区域的数量.

样例1

输入

3
2

输出

解释

最少能规划块 $3$ 个区域。
先规划 $1$ 个 $2$ $\times$ $2$
剩下区域规划 $2$ 个 $1$ $\times$ $1$

样例2

输入

13
11

输出

解释

最少能规划块 $6$ .个区域。

先规划 $1$ 个 $7$ $\times$ $7$ 和 $1$ 个 $6$ $\times$ $6$

再规划 $2$ 个 $4$ $\times$ $4$ 和 $1$ 个 $5$ $\times$ $5$

最后剩下 $1$ 个 $1$ $\times$ $1$

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LkyMPpok-1687435245505)(/split.png)]

思路：搜索+剪枝

给定一个 $n * m$ 的矩形，我们需要从中分割出若干个正方形，要求正方形个数最少，求该个数。

这道题初看很容易认为是用分治的做法，通过枚举分割长度将矩形分成两块，分别求两块最少能分割的正方形区域再相加，并不断递归求解。

先详细说明下错误的分治的做法：

假设当前矩形的长宽分别为 $a 、 b$ ，且有 $\gt b$

枚举分割长度 $i$ $\le i \lt a)$ ，从而得到两个大小的矩形 $i * b$ 和 $(a - i) * b$
将两个矩形当成子问题，即求解两个矩形最少能分割出多少正方形，于是又回到第一步
直到到达边界条件 $a = b$ ，此时能分割一个正方形，返回
在每次子问题求解完毕后，取两个子问题和的最小值作为当前矩形的最小值

但实际上看下样例2就会发现这样的解法是错误的，其分割方法很不规则，而分治的方法得到的分割方法很规则(因为每次都是整齐的分割成两个矩形，而样例2的分割是不整齐的)。分治在样例2上求出来的答案一般来说是8而不是6(可以自己尝试一下)。

由于样例2分割的不规则性，在发现分治无效后，也难以想到其它有效的解法。于是尝试使用搜索+剪枝求解。

(这其实是一个NP问题，但是当我们在比赛时，我们既不了解该问题，也不能想到有效的解法，就只能尝试用搜索方法尽可能拿分)

搜索规则如下：

定义 $matrix[i][j]=\left\{false,true\right\}$ 表示该点是否已经被分割为了一个正方形

找到一个 $ma t r i x [i] [j] = f a l se$ 的点，即该点未被分割为正方形
尝试以该点为正方形第一个点(即左上角点)分割正方形，即枚举正方形长度，尝试分割一个固定边长的正方形
将分割的区域标记为 $t r u e$ ，表示已经分割了正方形
重新回到第1步，直到无法找到未被标记的点

既然用了搜索，那肯定逃不掉的就是剪枝了，剪枝的方法有很多，这里提出几个主要的剪枝，有其它更优秀剪枝方法的可以自行添加：

记录当前已经找到的最小的答案，记为 $an s$ ，在搜索过程中，如果当前统计的分割的正方形数(记为 $c n t$ )，有 $\ge ans$ ，说明继续找下去答案也不会更优了，可以直接回退
枚举分割正方形的边长时，从大往小枚举，这样能够尽早找到一个较小的答案，从而在后续搜索中减少搜索量

搜索的时间复杂度很难衡量，所以这里就不进行时间复杂度的计算了。

类似题目推荐

代码

C++

#include <iostream>
#include <cstdio>
using namespace std;bool matrix[15][15];
int m,n;
int ans=1e9;bool check(int x,int y,int len){for(int i=0;i<len;++i){for(int j=0;j<len;++j){if(matrix[x+i][y+j]) return false;}}return true;
}void fill(int x,int y,int len){// 采用异或方法进行填充/取消填充 for(int i=0;i<len;++i){for(int j=0;j<len;++j){matrix[x+i][y+j]^=1;}}
} void dfs(int x, int y, int cnt){if(cnt>=ans) return;// 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索if(x==m+1){// 填充完毕，更新答案 ans=cnt;return;}if(y>n) dfs(x+1,1,cnt);bool full=true;for(int i=y;i<=n;++i){// 从当前行的第y个格子开始枚举，找到第一个没有填充的格子 if(!matrix[x][i]){// 当前格子未填充，尝试填充正方形 full=false;for(int j=min(n-i+1,m-x+1);j>=1;--j){// 枚举填充正方形的边长，从长边开始枚举 if(check(x,i,j)){// 判断从第x行第i个格子开始能不能填充边长为j的长方形 fill(x,i,j);// 填充dfs(x,y+j,cnt+1);// 填充完一个正方形，尝试下一次填充fill(x,i,j);// 取消填充 }}break;// 尝试在当前格子填充正方形的所有情况已经全部考虑，直接弹出 }}if(full) dfs(x+1,1,cnt);// 当前行都填充了，搜索下一行 
}int main(){scanf("%d %d",&m,&n);dfs(1,1,0);printf("%d",ans);return 0;
}

python

def check(x, y, length):# 判断从第x行第y个格子开始能否填充边长为length的正方形for i in range(length):for j in range(length):if matrix[x+i][y+j]:return Falsereturn Truedef fill(x, y, length):# 采用异或方法进行填充/取消填充for i in range(length):for j in range(length):matrix[x+i][y+j] ^= 1def dfs(x, y, cnt):global ansif cnt >= ans:return  # 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索if x == m + 1:ans = cnt  # 填充完毕，更新答案returnif y > n:dfs(x + 1, 1, cnt)full = Truefor i in range(y, n + 1):# 从当前行的第y个格子开始枚举，找到第一个没有填充的格子if not matrix[x][i]:  # 当前格子未填充，尝试填充正方形full = Falsefor j in range(min(n - i + 1, m - x + 1), 0, -1):# 枚举填充正方形的边长，从长边开始枚举if check(x, i, j):fill(x, i, j)  # 填充dfs(x, y + j, cnt + 1)  # 填充完一个正方形，尝试下一次填充fill(x, i, j)  # 取消填充break  # 尝试在当前格子填充正方形的所有情况已经全部考虑，直接跳出循环if full:dfs(x + 1, 1, cnt)  # 当前行都填充了，搜索下一行m, n = map(int, input().split())
matrix = [[False] * 15 for _ in range(15)]
ans = 1e9
dfs(1, 1, 0)
print(ans)

Java

import java.util.Scanner;public class Main {static boolean[][] matrix = new boolean[15][15];static int m, n;static int ans = (int) 1e9;static boolean check(int x, int y, int len) {// 判断从第x行第y个格子开始能否填充边长为len的正方形for (int i = 0; i < len; ++i) {for (int j = 0; j < len; ++j) {if (matrix[x + i][y + j])return false;}}return true;}static void fill(int x, int y, int len) {// 采用异或方法进行填充/取消填充for (int i = 0; i < len; ++i) {for (int j = 0; j < len; ++j) {matrix[x + i][y + j] ^= true;}}}static void dfs(int x, int y, int cnt) {if (cnt >= ans)return; // 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索if (x == m + 1) {ans = cnt; // 填充完毕，更新答案return;}if (y > n)dfs(x + 1, 1, cnt);boolean full = true;for (int i = y; i <= n; ++i) { // 从当前行的第y个格子开始枚举，找到第一个没有填充的格子if (!matrix[x][i]) { // 当前格子未填充，尝试填充正方形full = false;for (int j = Math.min(n - i + 1, m - x + 1); j >= 1; --j) { // 枚举填充正方形的边长，从长边开始枚举if (check(x, i, j)) { // 判断从第x行第i个格子开始能不能填充边长为j的正方形fill(x, i, j); // 填充dfs(x, y + j, cnt + 1); // 填充完一个正方形，尝试下一次填充fill(x, i, j); // 取消填充}}break; // 尝试在当前格子填充正方形的所有情况已经全部考虑，直接跳出循环}}if (full)dfs(x + 1, 1, cnt); // 当前行都填充了，搜索下一行}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);m = scanner.nextInt();n = scanner.nextInt();dfs(1, 1, 0);System.out.println(ans);scanner.close();}
}

Go

package mainimport "fmt"var matrix [15][15]bool
var m, n int
var ans = int(1e9)func check(x, y, length int) bool {// 判断从第x行第y个格子开始能否填充边长为length的正方形for i := 0; i < length; i++ {for j := 0; j < length; j++ {if matrix[x+i][y+j] {return false}}}return true
}func fill(x, y, length int) {// 采用异或方法进行填充/取消填充for i := 0; i < length; i++ {for j := 0; j < length; j++ {matrix[x+i][y+j] = !matrix[x+i][y+j]}}
}func dfs(x, y, cnt int) {if cnt >= ans {return // 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索}if x == m+1 {ans = cnt // 填充完毕，更新答案return}if y > n {dfs(x+1, 1, cnt)}full := truefor i := y; i <= n; i++ {// 从当前行的第y个格子开始枚举，找到第一个没有填充的格子if !matrix[x][i] {// 当前格子未填充，尝试填充正方形full = falsefor j := min(n-i+1, m-x+1); j >= 1; j-- {// 枚举填充正方形的边长，从长边开始枚举if check(x, i, j) {fill(x, i, j)         // 填充dfs(x, y+j, cnt+1)   // 填充完一个正方形，尝试下一次填充fill(x, i, j)         // 取消填充}}break // 尝试在当前格子填充正方形的所有情况已经全部考虑，直接跳出循环}}if full {dfs(x+1, 1, cnt) // 当前行都填充了，搜索下一行}
}func min(a, b int) int {if a < b {return a}return b
}func main() {fmt.Scan(&m, &n)dfs(1, 1, 0)fmt.Println(ans)
}

Js

function check(x, y, length) {// 判断从第x行第y个格子开始能否填充边长为length的正方形for (let i = 0; i < length; i++) {for (let j = 0; j < length; j++) {if (matrix[x + i][y + j]) {return false;}}}return true;
}function fill(x, y, length) {// 采用异或方法进行填充/取消填充for (let i = 0; i < length; i++) {for (let j = 0; j < length; j++) {matrix[x + i][y + j] = !matrix[x + i][y + j];}}
}function dfs(x, y, cnt) {if (cnt >= ans) {return; // 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索}if (x === m + 1) {ans = cnt; // 填充完毕，更新答案return;}if (y > n) {dfs(x + 1, 1, cnt);}let full = true;for (let i = y; i <= n; i++) {// 从当前行的第y个格子开始枚举，找到第一个没有填充的格子if (!matrix[x][i]) {// 当前格子未填充，尝试填充正方形full = false;for (let j = Math.min(n - i + 1, m - x + 1); j >= 1; j--) {// 枚举填充正方形的边长，从长边开始枚举if (check(x, i, j)) {fill(x, i, j); // 填充dfs(x, y + j, cnt + 1); // 填充完一个正方形，尝试下一次填充fill(x, i, j); // 取消填充}}break; // 尝试在当前格子填充正方形的所有情况已经全部考虑，直接跳出循环}}if (full) {dfs(x + 1, 1, cnt); // 当前行都填充了，搜索下一行}
}function main() {const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,});rl.on("line", (line) => {const input = line.split(" ").map(Number);m = input[0];n = input[1];rl.close();}).on("close", () => {matrix = new Array(15).fill(false).map(() => new Array(15).fill(false));dfs(1, 1, 0);console.log(ans);process.exit(0);});
}main();