[网络流24题]孤岛营救问题（状态压缩+搜索）

链接

题意：走迷宫问题，从（1，1）到（n，n）的最短时间，其中有墙，钥匙和门的设定。

做法：

广度优先搜索+钥匙串状态压缩

Q：可这和网络流有什么关系

A：标签：网络流24题，没了

UGLY Code：

#include<bits/stdc++.h>
#define N 200
using namespace std;
int n,m,p,s,k;
bool vis[15][15][1<<11];
int wall[15][15][15][15];
int key[15][15][15],sum[15][15];
int dox[4]={0,-1,0,1},doy[4]={1,0,-1,0};

template <class T>
void read(T &x)
{
	char c;int sign=1;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
	while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}

struct Node { int x,y,dis,key; };

int bfs()
{
	memset(vis,0,sizeof(vis));
	int k=0;for(int i=1;i<=sum[1][1];++i) k|=(1<<key[1][1][i]);
	queue<Node> q;
	q.push((Node){1,1,0,k});
	while(!q.empty())
	{
		Node u=q.front();q.pop();
		int x=u.x,y=u.y,d=u.dis,k=u.key;
		if(x==n&&y==m) return d;
		if(vis[x][y][k]) continue;
		vis[x][y][k]=1;
		for(int i=0;i<4;++i)
		{
			int dx=x+dox[i],dy=y+doy[i];
			if(dx<1||dy<1||dx>n||dy>m) continue;
			if(wall[x][y][dx][dy]==-1||(k>>wall[x][y][dx][dy]&1))
			{
				int bt=k;
				for(int j=1;j<=sum[dx][dy];++j) k|=(1<<key[dx][dy][j]);
				q.push((Node){dx,dy,d+1,k});
				k=bt;
			}
		}
	}
	return -1;
}
int main()
{
	memset(wall,-1,sizeof(wall));
	read(n);read(m);read(p);
	read(k);
	for(int i=1;i<=k;++i)
	{
		int x1,y1,x2,y2,opt;
		read(x1);read(y1);read(x2);read(y2);read(opt);
		wall[x1][y1][x2][y2]=wall[x2][y2][x1][y1]=opt;
	}
	read(s);
	for(int i=1;i<=s;++i)
	{
		int x,y,z;
		read(x);read(y);read(z);
		key[x][y][++sum[x][y]]=z;
	}
	cout<<bfs()<<endl;
	return 0;
}