[TIOJ] 1013. Fire in the forest

題目連結:http://tioj.infor.org/problems/1013
其實我覺得題敘沒講清楚,火只會跟人一樣蔓延在可以走的地方....
先BFS個每個點會在第幾分鐘被火燒到,注意E是不會被燒到的,所以可以偷偷先把它改成不可通行(?,之後再BFS一次找最短路徑。
#include <stdio.h>
#include <algorithm>
#include <queue>
#define INF 2147483647

using std::min;
using std::queue;

bool graph[10][17] = {
	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
	{0,1,1,1,0,1,1,1,1,1,1,1,0,0,1,1,0},
	{0,0,1,1,0,1,1,1,1,0,1,0,1,0,1,1,0},
	{0,1,1,1,1,1,1,0,1,0,0,1,0,0,1,0,0},
	{0,1,1,0,0,1,1,1,0,0,1,1,0,0,1,0,0},
	{0,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,0},
	{0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0},
	{0,1,1,1,1,1,0,0,0,0,1,0,1,1,1,0,0},
	{0,0,0,0,1,0,1,0,1,1,1,1,1,1,1,1,0},
	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
};

struct ff{
	int x,y,t;
};
struct mm{
	int x,y,t,v;
};

int tFire[10][17]={0};
int fX,fY;
int t;
int sX,sY, eX,eY;

int main(){
	scanf("%d%d%d%d%d%d%d",&fX,&fY,&t,&sX,&sY,&eX,&eY);
	graph[eX][eY]=0;
	queue<ff> q1;
	ff temp;
	temp.x=fX;
	temp.y=fY;
	temp.t=1;
	q1.push(temp);
	while(!q1.empty()){
		ff OAO = q1.front();
		q1.pop();
		tFire[OAO.x][OAO.y]=OAO.t;
		OAO.t++;
		if(OAO.x-1>=0 && graph[OAO.x-1][OAO.y] && tFire[OAO.x-1][OAO.y]==0){
			ff QAQ=OAO;
			QAQ.x--;
			q1.push(QAQ);
		}
		if(OAO.x+1<=9 && graph[OAO.x+1][OAO.y] && tFire[OAO.x+1][OAO.y]==0){
			ff QAQ=OAO;
			QAQ.x++;
			q1.push(QAQ);
		}
		if(OAO.y-1>=0 && graph[OAO.x][OAO.y-1] && tFire[OAO.x][OAO.y-1]==0){
			ff QAQ=OAO;
			QAQ.y--;
			q1.push(QAQ);
		}
		if(OAO.y+1<=16 && graph[OAO.x][OAO.y+1] && tFire[OAO.x][OAO.y+1]==0){
			ff QAQ=OAO;
			QAQ.y++;
			q1.push(QAQ);
		}
	}
	tFire[eX][eY]=INF;
	graph[eX][eY]=1;
	int r=INF;
	queue<mm> q2;
	mm tp;
	tp.x=sX;
	tp.y=sY;
	tp.t=t;
	tp.v=0;
	q2.push(tp);
	while(!q2.empty()){
		mm OAO = q2.front();
		q2.pop();
		if(tFire[OAO.x][OAO.y]<=OAO.t)continue;
		if(OAO.x==eX && OAO.y==eY) {r=min(r,OAO.v);break;}
		OAO.v++;
		OAO.t++;
		if(OAO.x-1>=0 && graph[OAO.x-1][OAO.y]){
			mm QAQ=OAO;
			QAQ.x--;
			q2.push(QAQ);
		}
		if(OAO.x+1<=9 && graph[OAO.x+1][OAO.y]){
			mm QAQ=OAO;
			QAQ.x++;
			q2.push(QAQ);
		}
		if(OAO.y-1>=0 && graph[OAO.x][OAO.y-1]){
			mm QAQ=OAO;
			QAQ.y--;
			q2.push(QAQ);
		}
		if(OAO.y+1<=16 && graph[OAO.x][OAO.y+1]){
			mm QAQ=OAO;
			QAQ.y++;
			q2.push(QAQ);
		}
	}
	if(r==INF)puts("Help!");
	else printf("%d",r);
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology