資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究用最少的正方形平鋪矩形（C++）
假設我們有一個大小為 n x m 的矩形。我們需要找到可以平鋪該矩形的最小數量的整數邊長方形物體。
因此，如果輸入像 n = 2 和 m = 3，
則輸出將為 3，因為我們需要三個塊。
為了解決這個問題，我們將遵循以下步驟：
定義一個對映 m
res := inf
定義一個函式 dfs()，它將接收 n、m、陣列 h、cnt，
如果 cnt >= res，則：
返回
isFull := true
pos := -1，minH := inf
初始化 i := 1，當 i <= n 時，更新（i 增加 1），執行：
如果 h[i] < m，則：
isFull := false
如果 h[i] < minH，則：
minH := h[i]
pos := i
如果 isFull 不為零，則：
res := res 和 cnt 的最小值
返回
key := 0
base := m + 1
初始化 i := 1，當 i <= n 時，更新（i 增加 1），執行：
key := key + h[i] * base
base := base * (m + 1)
如果 key 在 s 中並且 s[key] <= cnt，則：
返回
s[key] := cnt
end := pos
當 (end + 1 <= n 且 h[end + 1] 等於 h[pos] 且 (end + 1 - pos + 1 + minH)
<= m) 時，執行：
（end 增加 1）
初始化 j := end，當 j >= pos 時，更新（j 減小 1），執行：
curH := j - pos + 1
定義一個大小為 n + 1 的陣列 next
初始化 i := 1，當 i <= n 時，更新（i 增加 1），執行：
next[i] := h[i]
初始化 k := pos，當 k <= j 時，更新（k 增加 1），執行：
next[k] := next[k] + curH
dfs(n, m, next, cnt + 1)
從主方法執行以下操作：
如果 n 等於 m，則：
返回 1
如果 n > m，則
交換(n, m)
定義一個大小為 n + 1 的陣列 h
dfs(n, m, h, 0)
返回 res
讓我們看看以下實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map<int, int> s;
int res = INT_MAX;
void dfs(int n, int m, vector<int> h, int cnt){
if (cnt >= res)
return;
bool isFull = true;
int pos = -1, minH = INT_MAX;
for (int i = 1; i <= n; i++) {
if (h[i] < m)
isFull = false;
if (h[i] < minH) {
minH = h[i];
pos = i;
}
}
if (isFull) {
res = min(res, cnt);
return;
}
long key = 0;
long base = m + 1;
for (int i = 1; i <= n; i++) {
key += h[i] * base;
base *= m + 1;
}
if (s.find(key) != s.end() && s[key] <= cnt)
return;
s[key] = cnt;
int end = pos;
while (end + 1 <= n && h[end + 1] == h[pos] && (end + 1 - pos + 1 + minH) <= m)
end++;
for (int j = end; j >= pos; j--) {
int curH = j - pos + 1;
vector<int> next(n + 1);
for (int i = 1; i <= n; i++)
next[i] = h[i];
for (int k = pos; k <= j; k++) {
next[k] += curH;
}
dfs(n, m, next, cnt + 1);
}
}
int tilingRectangle(int n, int m){
if (n == m)
return 1;
if (n > m)
swap(n, m);
vector<int> h(n + 1);
dfs(n, m, h, 0);
return res;
}
};
main(){
Solution ob;
cout << (ob.tilingRectangle(2, 3));
}輸入
2,3
輸出
3
219 次瀏覽
