UVA11624 WA求改
查看原帖
UVA11624 WA求改
551088
FincheuwYggdrasil楼主2022/8/25 12:48

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()
{
	while(!q.empty())
	{
		pos 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(p.step + 1 < fire[xx][yy])
			{
				fire[xx][yy] = p.step + 1;
				q.push((pos){xx,yy,p.step + 1});
			}
		}
	}
}
void manfs(int x,int y)
{
	geta = false;
	while(!q.empty())
	{
		pos 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;
				q.push((pos){xx,yy,p.step + 1});
			}			
		}
	}
	if(!geta)
		printf("IMPOSSIBLE\n");
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= m;j++)
			{
				fire[i][j] = minn;
				vis[i][j] = 0;
			}
				
		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')
				{
					q.push((pos){i,j,0});
					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;
		}*/
		q.push((pos){sx,sy,0});
		memset(vis,false,sizeof(vis));
		manfs(sx,sy);
	}
 	return 0;
}
2022/8/25 12:48
加载中...