UVa 11624 Fire! / BFS

和普通BFS相比 多了個火

那麼先對火做一次BFS 預處理每個格子著火的時間

偷懶了 少開個數組 然後錯了半天

#include 
#include 
#include 
#include 
using namespace std;
const int MAX = 1010;
char a[MAX][MAX];
int map[MAX][MAX];
struct node
{
	int x;
	int y;
	int t;
}s;
int n, m;
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
bool bfs()
{
	queue  f;
	queue  q;
	memset(map,-1,sizeof(map));
	int i, j;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < m; j++)
		{
			if(a[i][j] == 'F')
			{
				node t;
				t.x = i;
				t.y = j;
				t.t = 0;
				f.push(t);
				map[i][j] = 0;
			}
			else if(a[i][j] == 'J')
			{
				node t;
				t.x = i;
				t.y = j;
				t.t = 0;
				q.push(t);
			}
		}
	}
	while(!f.empty())
	{
		node u = f.front();
		f.pop();
		for(i = 0; i < 4; i++)
		{
			node t;
			t.x = u.x + dir[i][0];
			t.y = u.y + dir[i][1];
			t.t = u.t + 1;
			if(t.x >= 0 && t.x < n && t.y >= 0 && t.y < m && a[t.x][t.y] != '#' && map[t.x][t.y] == -1)
			{
				map[t.x][t.y] = t.t;
				f.push(t);
			}
		}
	}
	/*for(i = 0;i < n; i++)
	{
		for(j = 0;j < m; j++)
			printf("%d ",map[i][j]);
		puts("");
	}*/
	while(!q.empty())
	{
		node u = q.front();
		q.pop();
		for(i = 0; i < 4; i++)
		{
			node t;
			t.x = u.x + dir[i][0];
			t.y = u.y + dir[i][1];
			t.t = u.t + 1;
			if(t.x < 0 || t.x >= n || t.y < 0 || t.y >= m)
			{
				printf("%d\n",t.t);
				return true;
			}
			if(t.x >= 0 && t.x < n && t.y >= 0 && t.y < m && a[t.x][t.y] != '#' && (map[t.x][t.y] > t.t || map[t.x][t.y] == -1))
			{
				a[t.x][t.y] = '#';
				q.push(t);
			}
		}
	}
	return false;
}
int main()
{
	int cas;
	int i, j;
	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d %d",&n,&m);
		for(i = 0; i < n; i++)
			scanf("%s",a[i]);
		if(!bfs())
			printf("IMPOSSIBLE\n");
	}
	return 0;
}