六边形平面

现在有一个N*N的六边形网格平面（这种平面类似蜂窝形状）。下图是N=1,2,3,4条件下的具体形状，根据它们可以依次类推N=5,6,....。 现在你需要对N*N网格中一些格子进行上色，在给定的输入中这些格子被标记上字符‘X’，而不用上色的网格被标记为‘-’。上色时需要注意，如果两个被上色的格子有公共边，那么这两个格子需要被涂成不同的颜色。问最少需要多少种颜色来完成任务？ Input 多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5 每组测试数据有相同的结构构成： 每组数据第一行一个整数N，表示网格大小，其中1<=N<=50. 之后有一个N*N的字符矩阵A，其中A(i,j)为‘X’表示网格中坐标为(i,j)的格子需要被上色，否则不用。 Output 每组数据一行输出，即最少需要的颜色数量. Input示例 3 3 --- --- --- 4 -X-- ---X ---- -X-- 4 XXXX ---X ---X ---X Output示例 0 1

2

#include <iostream> #include <cstring> #include <vector> using namespace std; const int MAXN = 55; int t; int n; char A[MAXN][MAXN]; int result = 0; bool circleFound = false; int offsetX[6] = {-1, -1, 0, 1, 1, 0}; int offsetY[6] = {0, 1, 1, 0, -1, -1}; bool used[MAXN][MAXN]; void findOddCircle(int x, int y, int num, int firstX, int firstY) { used[x][y] = true; for (int i = 0; i < 6; i++) { if ((x + offsetX[i] >= 0) && (x + offsetX[i] < n) && (y + offsetY[i] >= 0) && (y + offsetY[i] < n)) { if ((!used[x + offsetX[i]][y + offsetY[i]]) && (A[x + offsetX[i]][y + offsetY[i]] == 'X')) { findOddCircle(x + offsetX[i], y + offsetY[i], num + 1, firstX, firstY); if (circleFound) { break; } } else if (used[x + offsetX[i]][y + offsetY[i]]) { if ((num & 1) && (x + offsetX[i] == firstX) && (y + offsetY[i] == firstY)) { circleFound = true; break; } } } } } void cal(int i, int j) { bool firFound = false; int temp = 1; if ((j + 1 < n) && (A[i][j + 1] == 'X')) { firFound = true; temp++; } if ((i + 1 < n) && (A[i + 1][j] == 'X')) { temp++; } if (!firFound && (i + 1 < n) && (j - 1 >= 0) && (A[i + 1][j - 1] == 'X')) { temp++; } result = max(result, temp); } int main() { cin >> t; for (int i = 0; i < t; i++) { cin >> n; for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { cin >> A[j][k]; } } result = 0; for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { if (A[j][k] == 'X') { cal(j, k); } } } if (result < 3) { circleFound = false; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (A[i][j] == 'X') { memset(used, 0, sizeof(used)); findOddCircle(i, j, 1, i, j); if (circleFound) { result = 3; break; } } } if (circleFound) { break; } } } cout << result << endl; } return 0; }