BZOJ3393 [Usaco2009 Jan]Laserphones 激光通讯 BFS

原文链接http://www.cnblogs.com/zhouzhendong/p/8371735.html

---

题目传送门 - BZOJ3393

---

题意概括

　　直接看原题的翻译吧，很容易懂的。

　　

---

题解

　　我不知道这道题为什么放在网络流里面。

　　我也不知道网上为什么几乎都是SPFA。

　　这题就是一个裸的广搜啊啊啊。

　　20ms通过。

　　我们来考虑广搜。

　　只有改变方向是要花费的。

　　所以，我们入队的时候是一条线上的一起入队。

　　具体看我的pushnew函数。

　　然后主要的BFS循环内，只要扩展转弯就可以了（参见代码）。

　　我们考虑到，我这样做会导致在一个位置上进行多次转弯。

　　多次转弯，貌似是错的，但是由于本题特殊，这样一定是亏的，不会作为最优方案。

　　大概分成两种情况。

　　我们考虑如果只转了一次，显然是对的。

　　如果转了3次及以上，显然是亏的。

　　如果转了2次，只有可能：

　　　　1.原方向行进，显然是亏的。

　　　　2.原路返回，显然也是亏的。（自己脑补一下）

　　还有一个疑惑：比如下图的路线是否可能为最优路线（我的算法有可能会搜出这样的路线）：

　　

　　于是在(0,5)这个位置的镜子显然不对了。

　　但是这个显然不会是最优路线，直接挂掉。

---

代码

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cstdio>

#include <cmath>

using namespace std;

const int WH=105,N=4*WH*WH;

int w,h,S,E,dis[N],vis[N],q[N],head,tail;

char g[WH][WH];

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

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

char gc(){

	char ch=getchar();

	while (ch!='.'&&ch!='*'&&ch!='C')

		ch=getchar();

	return ch;

}

bool check(int x,int y){

	return 1<=x&&x<=w&&1<=y&&y<=h&&g[x][y]!='*';

}

int HA(int dir,int x,int y){

	return dir*w*h+(x-1)*h+y-1;

}

void HB(int v,int &dir,int &x,int &y){

	dir=v/w/h,v%=w*h,x=v/h+1,y=v%h+1;

}

bool covered(int v1,int v2){

	return v1%(w*h)==v2%(w*h);

}

void pushnew(int dir,int x,int y,int d){

	while (check(x,y)){

		int i=HA(dir,x,y);

		if (vis[i])

			break;

		vis[i]=1,dis[i]=d;

		q[++tail]=i;

		x+=dx[dir],y+=dy[dir];

	}

}

int main(){

	scanf("%d%d",&h,&w);

	for (int i=1;i<=w;i++)

		for (int j=1;j<=h;j++)

			g[i][j]=gc();

	S=E=-1;

	for (int i=1;i<=w;i++)

		for (int j=1;j<=h;j++)

			if (g[i][j]=='C')

				if (!~S)

					S=(i-1)*h+j-1;

				else

					E=(i-1)*h+j-1;

	memset(vis,0,sizeof vis);

	head=tail=0;

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

		dis[HA(i,E/h+1,E%h+1)]=w*h;

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

		pushnew(i,S/h+1,S%h+1,0);

	while (head<tail){

		int v=q[++head],dir,x,y;

		if (covered(v,E))

			break;

		HB(v,dir,x,y);

		pushnew((dir+1)%4,x,y,dis[v]+1);

		pushnew((dir+3)%4,x,y,dis[v]+1);

	}

	int ans=w*h;

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

		ans=min(ans,dis[HA(i,E/h+1,E%h+1)]);

	printf("%d",ans);

	return 0;

}