题目分析

这道题目描述了一个迷宫寻宝问题，主要特点包括：

1. 迷宫结构：由字符矩阵表示的迷宫，包含墙壁、通道、石块和宝藏
2. 移动规则：只能上下左右移动，不能穿过墙壁(*)
3. 障碍物：数字石块(1-9)需要时间或炸药来清除
4. 入口点：边界上的入口门(#或A-Z)，部分带有炸药包
5. 目标：从任意入口进入，找到到达宝藏($)的最短时间

解题思路

1. 状态表示：

   • 使用三元组(r,c,nTNT)表示状态：位置(r,c)和剩余炸药数量nTNT
   • state[r][c][nTNT]记录到达该状态的最小时间

2. 广度优先搜索(BFS)：

   • 从所有可能的入口门同时开始搜索
   • 对每个状态考虑四种移动方向
   • 遇到石块时有两种选择：使用炸药(时间+0)或等待(时间+石块硬度)
   • 遇到宝藏时更新最短时间

3. 关键优化：

   • 状态剪枝：只保留到达同一位置和炸药数量时的最短时间
   • 优先队列：可以改用Dijkstra算法处理不同时间消耗

标准代码实现

#include <iostream>  // 添加这一行以使用std::getline
#include <string>    // 添加这一行以使用std::string
#include<cstdio>
#include<cstring>
#include<ctype.h>
using namespace std;
const int maxn=1000000+3;
const int maxr=110;//如果开105就是 runtimeerror
const int maxc=110;
int R,C;
int dr[]={-1,1,0,0};//上,下,左,右
int dc[]={0,0,-1,1};
struct node
{
	int r,c,nTNT;
	int time;
	node(){}
	node(int r,int c,int nTNT,int time):r(r),c(c),nTNT(nTNT),time(time){}
}Q[maxn];//队列
int state[maxr][maxc][27];//记录到达该状态的最小时间
bool check(int r,int c,int nTNT,int t)
{
	return (state[r][c][nTNT]==-1 || state[r][c][nTNT]>t);
}
char map[maxr][maxc];//保存地图信息
int BFS()
{
	int front=0,tail=0;
	int ans=1000000;
	memset(state,-1,sizeof(state));
	for(int i=0;i<R;i++)                        //边缘入口进队列
		for(int j=0;j<C;j++)if(isupper(map[i][j]) || map[i][j]=='#')
	{
		Q[tail].r=i;
		Q[tail].c=j;
		Q[tail].nTNT=map[i][j]=='#'?0:map[i][j]-'A'+1;
		Q[tail].time=0;
		state[i][j][Q[tail].nTNT]=0;            //错误1 这里漏了
		tail++;
	}
	while(front<tail)
	{
		for(int d=0;d<4;d++)
		{
			int nr=Q[front].r+dr[d];
			int nc=Q[front].c+dc[d];
			int nTNT=Q[front].nTNT;
			int time=Q[front].time;
			if(nr>=1&&nr<=R-1&&nc>=1&&nc<=C-1&&map[nr][nc]!='*')
			{
				if(map[nr][nc]=='.' && check(nr,nc,nTNT,time))
				{
					state[nr][nc][nTNT]=time;
					Q[tail]=node(nr,nc,nTNT,time);
					tail++;//也可以这么写进行剪枝 if(que[tail].time<ans) tail++;
				}
				else if(isdigit(map[nr][nc]))//数字墙
				{
					if(nTNT>0 && check(nr,nc,nTNT-1,time))//炸开
					{
						state[nr][nc][nTNT-1]=time;
						Q[tail]=node(nr,nc,nTNT-1,time);
						tail++;//也可以这么写进行剪枝 if(que[tail].time<ans) tail++;
					}
					if(check(nr,nc,nTNT,time+map[nr][nc]-'0'))//花时间打开
					{
						state[nr][nc][nTNT]=time+map[nr][nc]-'0';
						Q[tail]=node(nr,nc,nTNT,time+map[nr][nc]-'0');
						tail++;//也可以这么写进行剪枝 if(que[tail].time<ans) tail++;
					}
				}
				else if(map[nr][nc]=='$')
				{
					if(ans>time) ans=time;
				}
			}
		}
		front++;
	}
	return ans;
}
int main()
{
	while(true)
	{
		R=C=0;
		std::string line;  // 用于存储读取的行
		while(std::getline(std::cin, line))  // 使用std::getline替代gets
		{
			if(line.empty()) break;  // 空行表示输入结束
			if(line[0]=='-') return 0;  // 以'-'开头的行表示程序结束
			
			// 将读取的行复制到map数组中
			std::strncpy(map[R], line.c_str(), maxc-1);
			map[R][maxc-1] = '\0';  // 确保字符串以空字符结尾
			R++;
		}
		if(R == 0) break;  // 如果没有读取到任何行，退出循环
		C = std::strlen(map[0]);
		int ans=BFS();
		if(ans==1000000) printf("IMPOSSIBLE\n");
		else printf("%d\n",ans);
	}
	return 0;
}

代码解析

1. 数据结构：

   • State结构体保存当前位置、剩余炸药和已用时间
   • dist数组记录到达各状态的最短时间

2. BFS实现：

   • 初始化时将所有入口门加入队列
   • 对每个状态扩展四种移动方向
   • 处理普通通道、石块和宝藏三种情况

3. 输入处理：

   • 逐行读取地图直到空行或结束标记
   • 处理换行符和边界条件

4. 输出结果：

   • 返回最短时间或IMPOSSIBLE

该解法通过状态空间搜索确保找到最优解，时间复杂度为O(R×C×T)，其中T是最大炸药数量(26)。