크기가 n x m인 직사각형이 있다고 가정합니다. 직사각형을 타일링할 수 있는 정사각형 개체의 최소 개수를 찾아야 합니다.
따라서 입력이 n =2 및 m =3인 경우
3개의 블록이 필요하므로 출력은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 맵 정의
-
res :=inf
-
dfs() 함수를 정의하면 n, m, 배열 h, cnt,
가 필요합니다. -
cnt>=res이면 -
-
반환
-
-
isFull :=참
-
위치 :=-1, 최소H :=정보
-
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
-
h[i]
-
isFull :=거짓
-
-
h[i]
-
minH :=h[i]
-
위치 :=나는
-
-
-
isFull이 0이 아니면 -
-
res :=res 및 cnt의 최소값
-
반환
-
-
키 :=0
-
기본 :=m + 1
-
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
-
키 :=키 + h[i] * 기본
-
기본 :=기본 * (m + 1)
-
-
키가 s 및 s[key] <=cnt에 있으면 -
-
반환
-
-
s[키] :=cnt
-
끝 :=위치
-
동안 (end + 1 <=n 및 h[end + 1]은 h[pos]와 동일하고 (end + 1 - pos + 1 + minH)
-
<=m), ~
-
(끝을 1씩 증가)
-
-
초기화 j :=end, j>=pos일 때 업데이트(j를 1만큼 감소), −
-
curH :=j - 위치 + 1
-
n + 1 크기의 배열을 정의하십시오.
-
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
-
다음[i] :=h[i]
-
-
초기화 k :=pos의 경우 k <=j일 때 업데이트(k를 1만큼 증가), −
-
다음[k] :=다음[k] + curH
-
-
dfs(n, m, 다음, cnt + 1)
-
-
주요 방법에서 다음을 수행하십시오 -
-
n이 m과 같으면 -
-
1 반환
-
-
n> m이면
-
스왑(n, m)
-
-
n + 1 크기의 배열 h 정의
-
dfs(n, m, h, 0)
-
반환 해상도
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#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