洛谷题解 P2937 【[USACO09JAN]激光电话Laserphones】

看到这题，一下就想到了爆搜。（不过这题输入也是够坑的）

单纯的搜索肯定是会超时的，所以这里需要考虑一些剪枝。

我们令bin[i][j][k]为在第i行j列时，方向为k的最小镜子数，若当时的镜子数已大于或等于此记录，那么就不必要更新了

否则往该点的四个方向进行更新：

方向相同

没必要放镜子了

方向相反

不存在这种可能，忽略（否则你的镜子要怎么放呢？）

其他

放一面镜子，更新方向

BFS代码：

#include<bits/stdc++.h>

using namespace std;

const int MAXN=100+10;

char Map[MAXN][MAXN];

int n,m;

int bx,by,ex,ey;

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

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

int ans=0x3f3f3f3f;

int bin[MAXN][MAXN][5];//剪枝用

struct Node

{

	int x,y;

	int cnt;

	int dir;//表示的方向

	/*

	1:right

	2:down

	3:left

	4:up

	*/

};

inline int read()

{

	int tot=0;

	char c=getchar();

	while(c<'0'||c>'9')

		c=getchar();

	while(c>='0'&&c<='9')

	{

		tot=tot*10+c-'0';

		c=getchar();

	}

	return tot;

}

inline void BFS()

{

	queue<Node>q;

	q.push((Node){bx,by,0,1});//推四种方向到队列中

	q.push((Node){bx,by,0,2});

	q.push((Node){bx,by,0,3});

	q.push((Node){bx,by,0,4});

	bin[bx][by][1]=bin[bx][by][2]=bin[bx][by][3]=bin[bx][by][4]=0;

	while(q.size())

	{

		Node now=q.front();

		//cout<<now.x<<" "<<now.y<<" "<<now.cnt<<" "<<now.dir<<endl;

		q.pop();

		if(now.cnt>=ans)continue;

		if(now.x==ex&&now.y==ey)

		{

			ans=min(ans,now.cnt);//更新答案

			continue;//注意：这里不能用break

		}

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

		{

			int a=dx[i]+now.x,b=dy[i]+now.y;

			if(a<1||b<1||a>n||b>m)continue;

			if(now.cnt>=bin[a][b][i])continue;//没必要更新了

			if(Map[a][b]=='*')continue;

			if(now.dir==i)

			{

				q.push((Node){a,b,now.cnt,i});

				bin[a][b][i]=now.cnt;//更新最小值

			}

			else

			{

				if(now.dir+i==4)continue;//这是方向相反时，看不懂的回去看一下各个数字代表的方向

				q.push((Node){a,b,now.cnt+1,i});

				bin[a][b][i]=now.cnt+1;//更新最小值

			}

		}

	}

}

int main()

{

	m=read();n=read();

	memset(bin,0x3f3f3f3f,sizeof(bin));//赋初值

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

	{

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

		{

			cin>>Map[i][j];

			if(Map[i][j]=='C'&&!bx&&!by)bx=i,by=j;//寻找起点

			else if(Map[i][j]=='C')ex=i,ey=j;//寻找终点

		}

	}

	BFS();

	/*for(int i=1;i<=n;i++)

	{

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

		{

			for(int k=1;k<=4;k++)cout<<bin[i][j][k]<<" ";

			cout<<endl;

		}

		cout<<endl<<endl;

	}*/

	cout<<ans<<endl;

	return 0;

}

巴特西

洛谷题解 P2937 【[USACO09JAN]激光电话Laserphones】

最新文章

热门文章

巴特西

洛谷 题解 P2937 【[USACO09JAN]激光电话Laserphones】

最新文章

热门文章

洛谷题解 P2937 【[USACO09JAN]激光电话Laserphones】