UVA11624求助
查看原帖
UVA11624求助
551088
FincheuwYggdrasil楼主2022/8/24 14:02

rt这个程序只输出impossible

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


2022/8/24 14:02
加载中...