样例过了提交没过求助
查看原帖
样例过了提交没过求助
551088
FincheuwYggdrasil楼主2022/8/25 10:38

rt

#include<bits/stdc++.h>
using namespace std;
const int minn = 2147483647;
int n,m,fire[1010][1010],sx,sy;
bool geta;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
bool vis[1010][1010];
char mapa[1010][1010];
struct pos{
	int x,y,step;
};
queue<pos> q;
void firefs()
{
	pos p,r;
	while(!q.empty())
	{
		p = q.front();
		q.pop();
		for(int i = 0;i < 4;i++)
		{
			int xx = dx[i] + p.x;
			int yy = dy[i] + p.y;
			vis[xx][yy] = true;
			if(p.step + 1 < fire[xx][yy])
			{
				r.step = p.step + 1;
				r.x = xx;
				r.y = yy;
				fire[r.x][r.y] = r.step;
				q.push(r);
			}
		}
	}
}
void manfs(int x,int y)
{
	pos p,r;
	p.x = x;
	p.y = y;
	p.step = 0;
	q.push(p);
	memset(vis,false,sizeof(vis));
	geta = false;
	while(!q.empty())
	{
		p = q.front();
		q.pop();
		if(p.x == 1 || p.y == 1 || p.x == n || p.y == m)
		{
			geta = true;
			printf("%d\n",p.step + 1);
			break;
		} 
		for(int i = 0;i < 4;i++)
		{
			int xx = dx[i] + p.x;
			int yy = dy[i] + p.y;
			if(p.step + 1 < fire[xx][yy] && !vis[xx][yy])
			{
				vis[xx][yy] = true;
				r.step = p.step + 1;
				r.x = xx;
				r.y = yy;
				q.push(r);
			}			
		}
	}
	if(!geta)
		printf("IMPOSSIBLE\n");
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int i = 0;i < t;i++)
	{
		memset(vis,false,sizeof(vis));
		scanf("%d%d",&n,&m);
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= m;j++)
				fire[i][j] = minn;
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= m;j++)
			{
				cin >> mapa[i][j];
				if(mapa[i][j] == 'J')
				{
					sx = i;
					sy = j;
				}
				if(mapa[i][j] == '#')
					fire[i][j] = 0;
				if(mapa[i][j] == 'F')
				{
					pos a;
					a.x = i;
					a.y = j;
					a.step = 0;
					q.push(a);
					vis[i][j] = true;
					fire[i][j] = 0;
				}	
			}
		firefs();
		/*for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= m;j++)
				printf("%d ",fire[i][j]);
			cout << endl;
		}*/
		manfs(sx,sy);
	}
 	return 0;
}


2022/8/25 10:38
加载中...