2016年11月10日 星期四

TIOJ 1013 - Fire in the forest

http://tioj.infor.org/problems/1013

 就火跟人一起BFS就好了
然後人不能走的地方火也不能走
我當初卡這個卡好久 不知道在幹嘛((

 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;

inline int rit(){
    int t=0,k=1;
    char c;
    do{
        c=getchar();
        if(c=='-')k=-1;
    }while(c<'0'||c>'9');
    do{
        t=t*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return t*k;
};

struct pnt{
    int x,y,len;
    pnt():x(0),y(0),len(0){};
    pnt(int xx,int yy,int lll):x(xx),y(yy),len(lll){};
};

string mp[10]={
    "*****************",
    "*...*.......**..*",
    "**..*....*.*.*..*",
    "*......*.**.**.**",
    "*..**...**..**.**",
    "**.....**..*.*..*",
    "*....*..........*",
    "*.....****.*...**",
    "****.*.*........*",
    "*****************"
};
int n,m,t;
int fx,fy,sx,sy,ex,ey;
bool gone[20][20],fgone[20][20];

queue<pnt> fq,mq;

void fWalk(){
    if(fq.empty())return;
    int time = fq.front().len;
    while(fq.size() && fq.front().len==time){
        pnt tmp = fq.front();fq.pop();
        int x = tmp.x,y = tmp.y,len = tmp.len;
        if(!fgone[x+1][y] && (mp[x+1][y]=='.' || mp[x+1][y]=='w') && x+1 <n){fgone[x+1][y]=1;mp[x+1][y]='*';fq.push({x+1,y,len+1});};
        if(!fgone[x-1][y] && (mp[x-1][y]=='.' || mp[x-1][y]=='w') && x-1>=0){fgone[x-1][y]=1;mp[x-1][y]='*';fq.push({x-1,y,len+1});};
        if(!fgone[x][y+1] && (mp[x][y+1]=='.' || mp[x][y+1]=='w') && y+1 <m){fgone[x][y+1]=1;mp[x][y+1]='*';fq.push({x,y+1,len+1});};
        if(!fgone[x][y-1] && (mp[x][y-1]=='.' || mp[x][y-1]=='w') && y-1>=0){fgone[x][y-1]=1;mp[x][y-1]='*';fq.push({x,y-1,len+1});};
    }
}

int meGo(){
    if(mq.empty())return -1;
    int time = mq.front().len;
    while(mq.size() && mq.front().len==time){
        pnt tmp = mq.front();mq.pop();
        int x=tmp.x, y=tmp.y, len=tmp.len; if(mp[x][y]=='*') continue;
        if(mp[x][y]=='!' || (x==ex && y==ey))return len;
        if(!gone[x+1][y] && mp[x+1][y]!='*'){if(mp[x+1][y]!='!'){mp[x+1][y]='w';}if(mp[x+1][y]=='!'){return len+1;}gone[x+1][y]=1;mq.push({x+1,y,len+1});};
        if(!gone[x-1][y] && mp[x-1][y]!='*'){if(mp[x-1][y]!='!'){mp[x-1][y]='w';}if(mp[x-1][y]=='!'){return len+1;}gone[x-1][y]=1;mq.push({x-1,y,len+1});};
        if(!gone[x][y+1] && mp[x][y+1]!='*'){if(mp[x][y+1]!='!'){mp[x][y+1]='w';}if(mp[x][y+1]=='!'){return len+1;}gone[x][y+1]=1;mq.push({x,y+1,len+1});};
        if(!gone[x][y-1] && mp[x][y-1]!='*'){if(mp[x][y-1]!='!'){mp[x][y-1]='w';}if(mp[x][y-1]=='!'){return len+1;}gone[x][y-1]=1;mq.push({x,y-1,len+1});};
    }
    return -1;
}

void P(){
    cout<<"now map:\n";
    for(int i=0;i<n;i++){
        cout<<mp[i]<<endl;
    }
    cout<<endl;
}

void S(){
    fq.push({fx,fy,0});
    mp[fx][fy]='*';
    fgone[fx][fy]=1;
    // cout<<"Init map: ";
    // P();
    for(int time=1;time<t;time++){
        fWalk();
        // P();
    }
    // P();
    // cout<<"pre gone.\n\n";

    mq.push({sx,sy,0});
    gone[sx][sy]=1;
    int cnt=1200;
    while(mq.size()){
        int res = meGo();
        if(res!=-1){
            cout<<res<<endl;
            return;
        }
        fWalk();
        // P();
    }
    cout<<"Help!\n";
}

int main(){
    n=10,m=17;
    fx=rit(),fy=rit(),t=rit(),sx=rit(),sy=rit(),ex=rit(),ey=rit();

    mp[ex][ey]='!';

    S();
}
張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)