Помогите! Нужен код на с++, который является решением этой задачи:
Дана полоска из M x N квадратов. Нужно замостить её прямоугольниками 2 x 3 без перекрытий и выходов за пределы полосы. Сколько различных вариантов замощения существует? Гарантируется, что при заданных M и N замощение возможно?
Ответы
#include <iostream>
#include <map>
#include <utility>
std::map<std::pair<int, int>, long long> memo;
long long waysToTile(int M, int N) {
if (M == 0 || N == 0) return 0;
if (M == 2 && N == 3) return 1;
if (M == 3 && N == 2) return 1;
if (M * N % 6 != 0) return 0; // Учитывая размер прямоугольника 2x3, общая площадь должна быть кратна 6
std::pair<int, int> key = {M, N};
if (memo.find(key) != memo.end()) {
return memo[key];
}
long long res = 0;
// Горизонтальное положение
if (M - 2 >= 0) {
res += waysToTile(M - 2, N);
}
if (N - 2 >= 0) {
res += waysToTile(M, N - 2);
}
// Вертикальное положение
if (N - 3 >= 0) {
res += waysToTile(M, N - 3);
}
if (M - 3 >= 0) {
res += waysToTile(M - 3, N);
}
memo[key] = res;
return res;
}
int main() {
int M, N;
std::cin >> M >> N;
std::cout << waysToTile(M, N) << std::endl;
return 0;
}