说明

本题模拟了参与者在一个由六边形瓷砖组成的街道上移动的过程。每个瓷砖的状态（热或冷）会随时间变化，参与者只能在冷瓷砖上移动。目标是找到参与者从第一行移动到最后一行的最短时间，或判断是否不可能。

算法标签

• 模拟：模拟瓷砖状态随时间的变化
• 广度优先搜索（BFS）：寻找最短路径
• 状态转换：根据规则更新瓷砖状态

解题思路

1. 问题分析：

   • 瓷砖状态变化遵循特定规则：热瓷砖在周围有3块冷瓷砖时变冷，冷瓷砖在周围有2或3块冷瓷砖时保持冷，否则变热。
   • 参与者只能在冷瓷砖上移动，可以留在原地或移动到相邻的冷瓷砖。
   • 需要在最短时间内从第一行移动到最后一行。

2. 关键步骤：

   • 预处理每个时间点的瓷砖状态矩阵。
   • 使用BFS从第一行的冷瓷砖出发，逐时间步扩展可达位置。
   • 检查是否到达最后一行，记录最短时间。

3. 算法选择：

   • 使用两个二维数组交替存储当前和下一个时间点的瓷砖状态。
   • BFS队列记录每个时间点可以到达的位置。
   • 提前终止条件：到达最后一行或超过时间限制（1000秒）。

分析

1. 输入处理：

   • 读取测试用例数，每个测试用例的行数N和列数M。
   • 读取初始瓷砖状态（'H'表示热，'C'表示冷）。

2. 状态转换：

   • 根据当前瓷砖状态和周围冷瓷砖数量，更新下一时间点的状态。
   • 使用两个数组交替存储状态，节省空间。

3. BFS搜索：

   • 初始化BFS队列，包含第一行的所有冷瓷砖。
   • 每个时间步，生成新的瓷砖状态，并更新可达位置。
   • 检查是否到达最后一行，若到达则记录时间并终止。

4. 结果输出：

   • 若找到路径，输出最短时间；否则输出"impossible"。

实现步骤

1. 读取输入：

   • 读取测试用例数T。
   • 对每个测试用例，读取N和M，以及初始瓷砖状态。

2. 初始化：

   • 预处理第一行的冷瓷砖作为BFS的起点。
   • 初始化状态矩阵和BFS队列。

3. 状态更新：

   • 对每个时间点，根据规则更新瓷砖状态。
   • 使用两个数组交替存储当前和下一时间点的状态。

4. BFS扩展：

   • 从当前时间点的可达位置出发，检查相邻瓷砖是否在下一时间点为冷。
   • 更新BFS队列，标记已访问位置。

5. 终止条件：

   • 若到达最后一行，记录时间并终止。
   • 若时间超过1000秒或无法继续前进，输出"impossible"。

6. 输出结果：

   • 根据是否找到路径，输出最短时间或"impossible"。

代码解释

• 输入处理：读取测试用例和初始瓷砖状态。
• 状态转换：根据规则计算每个时间点的瓷砖状态。
• BFS搜索：从起点出发，逐时间步扩展可达位置，检查是否到达终点。
• 结果输出：根据搜索情况输出最短时间或"impossible"。

该方法通过模拟瓷砖状态变化和BFS搜索，确保在合理时间内找到最短路径或判断无解。

代码

#include <iostream>
#include <stdio.h>
using namespace std;

int trans[2][7][2] = {{{-1,0},{-1,1},{0,-1},{0,1},{1,0},{1,1},{0,0}},
	{{-1,-1},{-1,0},{0,-1},{0,1},{1,-1},{1,0},{0,0}}};

struct pt{
	int x,y;
};

pt bfsList[1010][110];

int main() {
	int T;
	scanf("%d", &T);
	for(int ii = 0; ii < T;ii++){
		int N, M;
		scanf("%d%d", &N, &M);
		int bricks[2][15][15] = {0};
		for(int i = 1; i <= N; i++){
			char str[15];
			scanf("%s", str);
			for(int j = 1; j <= M; j++){
				char temp = str[j-1];
				if(temp == 'H') bricks[0][i][j] = 1;
				else bricks[0][i][j] = -1;
			}
		}
		if(N == 1){
			bool hasCold = 0;
			for(int i = 1; i <= M; i++){
				if(bricks[0][1][i] == -1){
					hasCold = 1;
					break;
				}
			}
			if(hasCold) printf("1\n");
			else printf("impossible\n");
			continue;
		}
		int bfsNum[1010] = {0};
		int minTime;
		bool ky = 0;
		for(int i = 1; i <= M; i++){
			if(bricks[0][1][i] == -1){
				bfsList[0][bfsNum[0]].x = 1;
				bfsList[0][bfsNum[0]].y = i;
				bfsNum[0]++;
			}
		}
		//首先计算下一秒的地圖
		for(int t = 1; t <= 999; t++){
			int from = (t+1)%2, to = t%2;
			for(int i = 1; i <= N; i++){
				for(int j = 1; j <= M; j++){
					int cnt = 0;
					for(int k = 0; k < 6; k++){
						if(bricks[from][i+trans[i%2][k][0]][j+trans[i%2][k][1]] == -1){
							cnt++;
						}
					}
					if(bricks[from][i][j] == 1){
						if(cnt == 3) bricks[to][i][j] = -1;
						else bricks[to][i][j] = 1;
					}
					else{
						if(cnt == 2 || cnt == 3){
							bricks[to][i][j] = -1;
						}
						else bricks[to][i][j] = 1;
					}
				}
			}
			bool used[15][15] = {0};
			for(int i = 0; i < bfsNum[t-1]; i++){
				int x = bfsList[t-1][i].x, y = bfsList[t-1][i].y;
				for(int k = 0; k < 7; k++){
					int X = x+trans[x%2][k][0], Y = y+trans[x%2][k][1];
					if(bricks[to][X][Y] == -1 && !used[X][Y]){
						if(X == N){
							minTime = t;
							ky = 1;
							goto done;
						}
						used[X][Y] = 1;
						bfsList[t][bfsNum[t]].x = X, bfsList[t][bfsNum[t]].y = Y;
						bfsNum[t]++;
					}
				}
			}
		}
		done:
			if(ky) printf("%d\n", minTime+1);
			else printf("impossible\n");
	}
	return 0;
}