HDU5094 Maze

知识点：状态压缩、bfs

题目链接

题意

$n\ast m$网格中一段网格线可能代表钥匙扣型号为$g_i$的锁住的门或墙（无法穿越网格线），方格可能代表存在多个型号为$q_i$的钥匙。你可以四面移动、携带钥匙和打开门，求从$(1,1)$到$(n,m)$的最短移动距离。

思路

此题不为状压dp，仅为状压。
关键在于记录携带钥匙信息，注意到p很小，考虑维护第i位（逆序）为i号钥匙是否携带，压缩成范围小于$2e3$($2^{10}$)的int类型，可作为数组下标，注意到n和m比较小，考虑bfs，且用vis[i][j][sta]表示是否有过走到(i,j)并且携带sta状态的钥匙的状态，可用于bfs剪枝，搜素范围为$n\ast m\ast 2^p<4e6$

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e2+10;
const ll M=1e4+10;
const ll inf=0x3f3f3f3f3f3f3f3f;

ll n,m,p;
ll door[2][N][N];//door[0][i][j]:(i,j)方格的下边为钥匙孔为
//door[0][i][j]的状态，door[1][i][j]:(i,j)方格的右边为钥匙孔为
//door[1][i][j]的状态
bool vis[N][N][M];//同上述思路
ll key[N][N];//(i,j)方格上有钥匙的sta状态（再次提醒：同一格钥匙有多个）
ll k,s;
ll dir[4][2]= {
   -1,0,0,0,0,0,0,-1};//选择(i,j)方格的4个边界
ll dir2[4][2]= {
   -1,0,0,1,1,0,0,-1};//正常的方向数组

//bfs维护的信息
struct node
{
   
	ll x,y,key,step;//x,y:坐标，key:携带钥匙的状态，step:走过的距离
};

void init()
{
   
	for(ll i=0; i<=n+5; i++)
		for(ll j=0; j<=m+5; j++)
		{
   
			key[i][j]=door[0][i][j]=door[1][i][j]=0;
			for(ll k=0; k<(1<<p+1)+5; k++)
				vis[i][j][k]=false;
		}
}

void solve()
{
   
	init();
	scanf("%lld",&k);
	while(k--)
	{
   
		ll xa,ya,xb,yb,g;
		scanf("%lld%lld%lld%lld%lld",&xa,&ya,&xb,&yb,&g);
		if(xa==xb)//需要水平通过的门（门在竖直方向的网格线上）
		{
   
			ll pos=min(ya,yb);//取左边方格
			if(g==0) door[1][xa][pos]=-1;//有墙记为-1
			else door[1][xa][pos]=1<<g-1;//钥匙孔状态，(1<<i)为存在i+1号钥匙孔
		}
		else//同理
		{
   
			ll pos=min(xa,xb);//取上边方格
			if(g==0) door[0][pos][ya]=-1;
			else door[0][pos][ya]=1<<g-1;
		}
	}
	scanf("%lld",&s);
	while(s--)
	{
   
		ll x,y,q;
		scanf("%lld%lld%lld",&x,&y,&q);
		key[x][y]|=1<<q-1;//钥匙状态，(1<<i)为存在i+1号钥匙
	}
	if(n==1&&m==1)
	{
   
		puts("0");
		return;
	}
	queue<node> que;
	que.push({
   1,1,key[1][1],0});
	vis[1][1][key[1][1]]=true;
	while(!que.empty())
	{
   
		node t=que.front();
		que.pop();
		//当前状态的四个方向
		for(ll i=0; i<4; i++)
		{
   
			ll x=t.x+dir2[i][0],y=t.y+dir2[i][1];//枚举方向后的方格位置
			if(x<1||x>n||y<1||y>m) continue;
			ll xx=t.x+dir[i][0],yy=t.y+dir[i][1];//枚举方向后的网格线方向（建议手动模拟）
			//剪枝，条件为为墙或(不为空且没有对应钥匙)，
			//i&1确定门的方向，对应方向数组，0为竖直方向，1为水平方向。
			if(door[i&1][xx][yy]==-1||
			door[i&1][xx][yy]!=0&&(t.key&door[i&1][xx][yy])==0) continue;
			ll sta=t.key|key[x][y];//更新状态
			if(vis[x][y][sta]) continue;
			vis[x][y][sta]=true;
			if(x==n&&y==m)
			{
   
				printf("%lld\n",t.step+1);
				return;
			}
			que.push({
   x,y,sta,t.step+1});
		}
	}
	puts("-1");
}

int main()
{
   
	while(~scanf("%lld%lld%lld",&n,&m,&p))
		solve();
	return 0;
}