제출 #255347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255347		DavidDamian	Mecho (IOI09_mecho)	C++11	100 / 100	223 ms	11388 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
///Binary Search
///BFS
///Determine the number of minutes that Mecho can stay eating honey (moment he leaves -1)
///Use two BFS, for the bees and for Mecho, second has parameter "fuel" since he can travel more than 1 step per minute
struct node
{
    int i,j;
    node(){}
    node(int i,int j) : i(i),j(j){}
};
int n,s;
char board[805][805];
int bee[805][805];
int d[805][805];
int color[805][805];
int fuel[805][805];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
queue<node> Q;
node start,finish;
void bfsBee()
{
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            bee[i][j]=INT_MAX;
            if(board[i][j]=='H'){
                Q.push(node(i,j));
                bee[i][j]=0;
                color[i][j]=-1;
            }
        }
    }
    while(Q.size()){
        node u=Q.front();Q.pop();
        for(int mov=0;mov<4;mov++){
            int i=u.i+dx[mov];
            int j=u.j+dy[mov];
            if(i<1 || i>n) continue;
            if(j<1 || j>n) continue;
            if(board[i][j]=='T' || board[i][j]=='D') continue;
            if(color[i][j]==0){
                color[i][j]=-1;
                Q.push(node(i,j));
                bee[i][j]=bee[u.i][u.j]+1;
            }
        }
    }
}
void bfsMecho(int init_d)
{
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            d[i][j]=INT_MAX;
            color[i][j]=0;
        }
    }
    if(bee[start.i][start.j]<=init_d-1) return;
    d[start.i][start.j]=init_d-1;
    fuel[start.i][start.j]=0;
    color[start.i][start.j]=init_d;
    Q.push(start);
    while(Q.size()){
        node u=Q.front();Q.pop();
        if(d[u.i][u.j]==bee[u.i][u.j] && fuel[u.i][u.j]==0) continue; //Bees caught Mecho
        for(int mov=0;mov<4;mov++){
            int i=u.i+dx[mov];
            int j=u.j+dy[mov];
            if(i<1 || i>n) continue;
            if(j<1 || j>n) continue;
            if(board[i][j]=='T') continue;
            if(color[i][j]!=init_d){
                d[i][j]=(fuel[u.i][u.j]>0)? d[u.i][u.j] : d[u.i][u.j]+1;
                if(bee[i][j]<d[i][j]) continue; //Already filled with bees
                fuel[i][j]=(fuel[u.i][u.j]>0)? fuel[u.i][u.j]-1 : s-1;
                color[i][j]=init_d;
                Q.push(node(i,j));
            }
        }
    }
}
bool valid(int k)
{
    bfsMecho(k);
    return d[finish.i][finish.j]!=INT_MAX;
}
int binarySearch()
{
    int k=0;
    for(int b=10000;b>=1;b/=2){
        while(valid(k+b)) k+=b;
    }
    return k-1;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>board[i][j];
            if(board[i][j]=='M') start={i,j};
            if(board[i][j]=='D') finish={i,j};
        }
    }
    bfsBee();
    int maximum=binarySearch();
    cout<<maximum<<'\n';
    return 0;
}

• Subtask 1: 100 / 100