[TIOJ] 1013. Fire in the forest
- 取得連結
- X
- 以電子郵件傳送
- 其他應用程式
題目連結:http://tioj.infor.org/problems/1013
其實我覺得題敘沒講清楚,火只會跟人一樣蔓延在可以走的地方....
先BFS個每個點會在第幾分鐘被火燒到,注意E是不會被燒到的,所以可以偷偷先把它改成不可通行(?,之後再BFS一次找最短路徑。
其實我覺得題敘沒講清楚,火只會跟人一樣蔓延在可以走的地方....
先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;
}
C++
留言
張貼留言