HDU 5094 Maze

话说这算是哪门子的撞鸭dp。。。

钥匙种类就 11 个，把有没有每种钥匙压成一个状态，然后 vis 数组多加一维钥匙的状态

bfs大模拟，没了~

#include <cstdio>
#include <cctype>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cstring>
#define reg register
using namespace std;
const int MaxN=51;
const int dir[4][2]={1,0,0,1,-1,0,0,-1};
struct Node
{
	int x,y;
	int step,key; 
};
template <class t> inline void rd(t &s)
{
	s=0;
	reg char c=getchar();
	while(!isdigit(c))
		c=getchar();
	while(isdigit(c))
		s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return;
}
int key[MaxN][MaxN];
bool vis[MaxN][MaxN][1<<12];
int block[MaxN][MaxN][MaxN][MaxN]; // -1 ??    0 ?????÷    >0?? 
int n,m,p,k,s;
inline void bfs()
{
	memset(vis,false,sizeof vis);
	queue<Node> Q;
	Q.push((Node){1,1,0,key[1][1]});
	vis[1][1][key[1][1]]=true;
	while(!Q.empty())
	{
		reg Node u=Q.front();Q.pop();
//		printf("--> %d %d %d %d\n",u.x,u.y,u.key,u.step);
		if(u.x==n&&u.y==m)
		{
			printf("%d\n",u.step);
			return;
		}
		for(int i=0;i<4;++i)
		{
			reg int nx=u.x+dir[i][0];
			reg int ny=u.y+dir[i][1];
			reg int nkey=u.key;
			if(nx&&nx<=n&&ny&&ny<=m)
				if(block[u.x][u.y][nx][ny]!=-1)
				{
					if(block[u.x][u.y][nx][ny])
						if(!(nkey&(1<<block[u.x][u.y][nx][ny])))
							continue;
					if(key[nx][ny])
						nkey|=key[nx][ny];
					if(vis[nx][ny][nkey])
						continue;
					vis[nx][ny][nkey]=true;
					Q.push((Node){nx,ny,u.step+1,nkey});
				}
		}
	} 
	puts("-1");
	return;
}
inline void Input()
{
	memset(key,0,sizeof key);
	memset(block,0,sizeof block);
	reg int a,b,c,d,x;
	rd(k);
	for(int i=1;i<=k;++i)
	{
		rd(a);rd(b);rd(c);rd(d);rd(x);
		if(!x)
			block[a][b][c][d]=block[c][d][a][b]=-1;
		else
			block[a][b][c][d]=block[c][d][a][b]=x;
	}
	rd(s);
	for(int i=1;i<=s;++i)
	{
		rd(a);rd(b);rd(x);
		key[a][b]|=(1<<x);
	}
	return;
}
signed main(void)
{
//	freopen("C - Maze.in","r",stdin);
	while(cin>>n>>m>>p)
		Input(),bfs();
	return 0;
}

HDU 5094 Maze

原文：https://www.cnblogs.com/chinesepikaync/p/12706256.html