【UVa】1601 The Morning after Halloween（双向bfs）

题目

题目

 

---

 

分析

双向bfs，对着书打的，我还调了好久。

 

---

 

代码

#include<cstdio>

#include<cstring>

#include<cctype>

#include<queue>

using namespace std;

const int maxs=20,maxn=150;

const int dx[]={1,-1,0,0,0},dy[]={0,0,1,-1,0};

int s[3],t[3];

int deg[maxn],G[maxn][5];

int dis[maxn][maxn][maxn],dis_back[maxn][maxn][maxn];

int id[maxn][maxn];

inline int ID(int a,int b,int c)

{

	return (a<<16)|(b<<8)|c;

}

inline bool conflict(int a,int b,int a2,int b2)

{

	return a2==b2 || (a2==b && b2==a);

}

int bfs(queue<int>& q,int d[maxn][maxn][maxn])

{

	int u=q.front(); q.pop();

	int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff;

	if(dis[a][b][c]!=-1 && dis_back[a][b][c]!=-1) return dis[a][b][c]+dis_back[a][b][c];

	for(int i=0;i<deg[a];i++)

	{

		int a2=G[a][i];

		for(int j=0;j<deg[b];j++)

		{

			int b2=G[b][j];

			if(conflict(a,b,a2,b2)) continue;

			for(int k=0;k<deg[c];k++)

			{

				int c2=G[c][k];

				if(conflict(a,c,a2,c2)) continue;

				if(conflict(b,c,b2,c2)) continue;

				if(d[a2][b2][c2]!=-1) continue;

				d[a2][b2][c2]=d[a][b][c]+1;

				q.push(ID(a2,b2,c2));

			}

		}

	}

	return -1;

}

int solve()

{

	queue<int> q;

	q.push(ID(s[0],s[1],s[2]));

	memset(dis,-1,sizeof(dis));

	dis[s[0]][s[1]][s[2]]=0;

	queue<int> q_back;

	q_back.push(ID(t[0],t[1],t[2]));

	memset(dis_back,-1,sizeof(dis_back));

	dis_back[t[0]][t[1]][t[2]]=0;

	int ans,t=0;

	while(1)

	{

		t++;

		ans=bfs(q,dis);

		if(ans!=-1) return ans;

		ans=bfs(q_back,dis_back);

		if(ans!=-1) return ans;

	}

	return -1;

}

int main()

{

	int w,h,n;

	while(scanf("%d%d%d",&w,&h,&n)==3 && n)

	{

		getchar();

		char maze[20][20];

		for(int i=0;i<h;i++) fgets(maze[i],20,stdin);

		int cnt=0,x[maxn],y[maxn],id[maxs][maxs];

		for(int i=0;i<h;i++)

		for(int j=0;j<w;j++)

		{

			char ch=maze[i][j];

			if(ch!='#')

			{

				x[cnt]=i; y[cnt]=j;

				id[i][j]=cnt;

				if(islower(ch)) s[ch-'a']=cnt;

				else if(isupper(ch)) t[ch-'A']=cnt;

				cnt++;

			}

		}

		for(int i=0;i<cnt;i++)

		{

			deg[i]=0;

			for(int dir=0;dir<5;dir++)

			{

				int nx=x[i]+dx[dir];

				int ny=y[i]+dy[dir];

				if(maze[nx][ny]!='#')

					G[i][deg[i]++]=id[nx][ny];

			}

		}

		if(n<=2) deg[cnt]=1,G[cnt][0]=cnt,s[2]=t[2]=cnt++;

		if(n<=1) deg[cnt]=1,G[cnt][0]=cnt,s[1]=t[1]=cnt++;

		printf("%d\n",solve());

	}

	return 0;

}