Submission #255227

#	Time	Username	Problem	Language	Result	Execution time	Memory
255227		DavidDamian	Mecho (IOI09_mecho)	C++11	21 / 100	1099 ms	6784 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int i,j;
    node(){}
    node(int i,int j) : i(i),j(j){}
};
int n,s;
char board[605][605];
int bee[605][605];
int d[605][605];
int color[605][605];
int fuel[605][605];
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;
        }
    }
    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();
        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;
                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=1000;b>=1;b/=2){
        while(valid(k+b)) k+=b;
    }
    return (k==0)? -1 : k;
}
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: 21 / 100