洛谷P2199 【最后的迷宫】题解

题目自己看，链接：最后的迷宫-洛谷

（脑袋有问题的人也知道这是道BFS题）

N×M≤16384，这道题本身内存有点小，极限数据是1≤N,M≤16384,因为N和M有可能是1。一开始我MLE了，但最终还是卡数据卡过去了。

话不多说，代码整上。

首先是最基本的头文件、变量、位移数组。

#include
using namespace std;
const int dx[]={1,0,-1,0,1,-1,1,-1};
const int dy[]={0,1,0,-1,1,1,-1,-1};
int n,m;
char mz[16395/2][16395/2];
int jbx,jby,hpx,hpy;
bool vis[16395/2][16395/2];

然后是check()函数，用于判断是否能看见奖杯。

bool check(int x,int y)
{
	for(int dir=0;dir<8;dir++)
	{
		int nx=x;
		int ny=y;
		if(nx==jbx&&ny==jby)return true;
		while(nx<=n&&nx>=1&&ny<=m&&ny>=1)
		{
			nx+=dx[dir];
			ny+=dy[dir];
			if(mz[nx][ny]=='X')break;
			if(nx==jbx&&ny==jby)return true;
		}
	}
	return false;
}

最后是主函数+BFS

int main(void)
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)cin>>mz[i][j];
	}
	do
	{
		queueqx;
		queueqy;
		queuestep;
		cin>>jbx>>jby>>hpx>>hpy;
		if(jbx==0&&jby==0&&hpx==0&&hpy==0)break;
		memset(vis,false,sizeof(vis));
		if(check(hpx,hpy))
		{
			cout<<0<n||ny<1||ny>m)continue;
				if(mz[nx][ny]=='X')continue;
				if(vis[nx][ny])continue;
				vis[nx][ny]=true;
				qx.push(nx);
				qy.push(ny);
				step.push(st+1);
				if(check(nx,ny))
				{
					cout< 
完整代码安排亿下
 
#include
using namespace std;
const int dx[]={1,0,-1,0,1,-1,1,-1};
const int dy[]={0,1,0,-1,1,1,-1,-1};
int n,m;
char mz[16395/2][16395/2];
int jbx,jby,hpx,hpy;
bool vis[16395/2][16395/2];
bool check(int x,int y)
{
	for(int dir=0;dir<8;dir++)
	{
		int nx=x;
		int ny=y;
		if(nx==jbx&&ny==jby)return true;
		while(nx<=n&&nx>=1&&ny<=m&&ny>=1)
		{
			nx+=dx[dir];
			ny+=dy[dir];
			if(mz[nx][ny]=='X')break;
			if(nx==jbx&&ny==jby)return true;
		}
	}
	return false;
}
int main(void)
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)cin>>mz[i][j];
	}
	do
	{
		queueqx;
		queueqy;
		queuestep;
		cin>>jbx>>jby>>hpx>>hpy;
		if(jbx==0&&jby==0&&hpx==0&&hpy==0)break;
		memset(vis,false,sizeof(vis));
		if(check(hpx,hpy))
		{
			cout<<0<n||ny<1||ny>m)continue;
				if(mz[nx][ny]=='X')continue;
				if(vis[nx][ny])continue;
				vis[nx][ny]=true;
				qx.push(nx);
				qy.push(ny);
				step.push(st+1);
				if(check(nx,ny))
				{
					cout<