Polyomino
大致题意
给定一个 4×44×4 的地图，地图上存在三个连通块，每个连通块用 # 连接。
现在你可以将这三个连通块任意平移、旋转到任何位置摆放，但你不可以翻转，问是否能刚好覆盖地图（即三个连通块不能有重合、超出地图或铺不满地图）。
解题思路
因为固定的有三个4X4的方块，所以可以直接暴力模拟，当时写的时候也想到模拟了，但是不知道怎么进行旋转就直接跳过了
重点说明一下旋转：
通过画图，很容易可以发现，i，j的旋转得到的是j，4-i+1,由此就可以得到旋转函数
// 旋转矩阵
void swp(int index) {for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {t[i][j] = sp[index][i][j];}}for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {sp[index][i][j] = t[4 - j + 1][i];}}
}
平移函数
/ 平移矩阵
bool py(int index, int x, int y) {for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {if (sp[index][i][j] == '#' &&(x + i > 4 || y + j > 4 || x + i < 1 || y + j < 1)) {return false;}}}return true;
}
所以完整的代码
#include <bits/stdc++.h>using namespace std;char s[4][5][5], sp[4][5][5], pt[4][5][5], t[5][5];
int vis[5][5], t1[4], t2[4];// 旋转矩阵
void swp(int index) {for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {t[i][j] = sp[index][i][j];}}for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {sp[index][i][j] = t[4 - j + 1][i];}}
}// 平移矩阵
bool py(int index, int x, int y) {for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {if (sp[index][i][j] == '#' &&(x + i > 4 || y + j > 4 || x + i < 1 || y + j < 1)) {return false;}}}return true;
}// 检查矩阵
bool check() {for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {if (vis[i][j] != 1) {return false;}}}return true;
}// 求最后的分布情况
void ok() {
//进行初始化for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {vis[i][j] = 0;}}for (int id = 1; id <= 3; id++) {for (int x = 1; x <= 4; x++) {for (int y = 1; y <= 4; y++) {vis[x + t1[id]][y + t2[id]] += pt[id][x][y] == '#';//只找#,其余的不记}}}
}// dfs 搜索
void dfs(int x) {
//表示当前已经枚举完三个4X4方块if (x > 3) {ok();if (check()) {cout << "Yes";exit(0);}return;}
//对代码进行复刻for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {sp[x][i][j] = s[x][i][j];}}for (int scnt = 1; scnt <= 3; scnt++) { // 枚举旋转次数for (int py1 = -4; py1 <= 4; py1++) { // 行偏移量for (int py2 = -4; py2 <= 4; py2++) { // 列偏移量if (py(x, py1, py2)) {for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {pt[x][i][j] = sp[x][i][j];}}t1[x] = py1, t2[x] = py2;//记录第x个方块的偏移量dfs(x + 1);}}}swp(x);//进行旋转}
}int main() {for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 4; j++) {for (int k = 1; k <= 4; k++) {cin >> s[i][j][k];}}}dfs(1);cout << "No";return 0;
}
