2023.05.31-暑期实习-第二题-园区规划

TaZi SU @ 7 months ago

思路：搜索+剪枝

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

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

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

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

枚举分割长度 $i$ $(1 \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\}$ 表示该点是否已经被分割为了一个正方形

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

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

记录当前已经找到的最小的答案，记为 $ans$ ，在搜索过程中，如果当前统计的分割的正方形数(记为 $cnt$ )，有 $cnt \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 False
    return True

def fill(x, y, length):
    # 采用异或方法进行填充/取消填充
    for i in range(length):
        for j in range(length):
            matrix[x+i][y+j] ^= 1

def dfs(x, y, cnt):
    global ans
    if cnt >= ans:
        return  # 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索
    if x == m + 1:
        ans = cnt  # 填充完毕，更新答案
        return
    if y > n:
        dfs(x + 1, 1, cnt)
    full = True
    for i in range(y, n + 1):
        # 从当前行的第y个格子开始枚举，找到第一个没有填充的格子
        if not matrix[x][i]:  # 当前格子未填充，尝试填充正方形
            full = False
            for 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 main

import "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 := true
	for i := y; i <= n; i++ {
		// 从当前行的第y个格子开始枚举，找到第一个没有填充的格子
		if !matrix[x][i] {
			 // 当前格子未填充，尝试填充正方形
			full = false
			for 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();

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

# Submissions

Accepted

Uploaded By

TaZi

1 solutions

思路：搜索+剪枝

代码

C++

python

Java

Go

Js

Information

Status

Development

Support