zoj 3810 A Volcanic Island(构造)

本文主要是介绍zoj 3810 A Volcanic Island(构造)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：zoj 3810 A Volcanic Island

题目大意：给定n，要求用n块面积为n的拼图铺满n∗n的矩阵，任意两块拼图形状不能相同（包括旋转和镜像），并且n块拼图只能有4中颜色，相邻两块拼图颜色不能相同。

解题思路：构造，n = 2，3，4时是不存在的。然后对于n >= 5的直接构造，具体看代码。注意这种构造方式构造6的时候会出现相同的拼图，所以特判。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 105;
const char s[10][10] = {"BBBBBB", "GGRGRR", "GRRGRB", "GRGGRB", "GRGRRB", "GRGBBB"};
const char c[5] = "BGRY";int g[maxn][maxn];void solve (int n) {memset(g, 0, sizeof(g));for (int i = 0; i < n; i++)g[0][i] = 3;int k = (n - 1) / 2, col = 1;for (int i = 0; i < k; i++) {for (int j = 1; j <= i+1; j++)g[j][i+1] = col;for (int j = i+1; j < n; j++)g[j][i] = col;col = 3 - col;}for (int i = k; i < n; i++) {for (int j = 2; j <= i+2; j++)g[j][i+2] = col;g[i+2][i+1] = col;for (int j = i+2; j < n; j++)g[j][i] = col;col = 3 - col;}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++)printf("%c", c[g[i][j]]);printf("\n");}
}int main () {int cas, n;scanf("%d", &cas);while (cas--) {scanf("%d", &n);if (n == 1)printf("B\n");else if (n == 6) {for (int i = 0; i < 6; i++)printf("%s\n", s[i]);} else if (n >= 5) {solve(n);} elseprintf("No solution!\n");}return 0;
}

这篇关于zoj 3810 A Volcanic Island(构造)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---