제출 #682837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682837		NONTAC	Mecho (IOI09_mecho)	C++11	84 / 100	249 ms	12236 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

int dx[4] = {0, -1, 1, 0};
int dy[4] = {1, 0, 0, -1};
long long n, s;
int si, sj, fi, fj;
char grid[802][802];
long long reach[802][802], d[802][802];
bool vis[802][802];

void print()
{
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) cout<<reach[i][j]<<" ";
        cout<<endl;
    }
}

void INIT()
{
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            vis[i][j] = false;
            d[i][j] = INT_MAX;
        }
    }
}

void flood()
{
    queue<ii> q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) if(grid[i][j] == 'H'){
            vis[i][j] = true;
            q.push(ii(i, j));
        }
    }
    while(!q.empty()){
        int ui = q.front().first, uj = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int vi = ui + dx[i], vj = uj + dy[i];
            if(vi >= 1 && vi <= n && vj >= 1 && vj <= n){
                if(!vis[vi][vj] && grid[vi][vj] != 'T' && grid[vi][vj] != 'D'){
                    vis[vi][vj] = true;
                    reach[vi][vj] = reach[ui][uj] + s;
                    q.push(ii(vi, vj));
                }
            }
        }
    }
}

bool check(long long k)
{
    INIT();
    d[si][sj] = k * s;
    reach[fi][fj] = INT_MAX;
    vis[si][sj] = true;
    queue<ii> q;
    q.push(ii(si, sj));
    while(!q.empty()){
        int ui = q.front().first, uj = q.front().second;
        q.pop();
        if((ui >= fi - 1 && ui <= fi + 1 && uj == fj)||(ui == fi && uj <= fj + 1 && uj >= fj - 1)){
            return true;
        }
        for(int i = 0; i < 4; i++){
            int vi = ui + dx[i], vj = uj + dy[i];
            if(vi < 1 || vi > n || vj < 1 || vj > n) continue;
            if(reach[vi][vj] > d[ui][uj] + 1 && !vis[vi][vj] && grid[vi][vj] != 'T'){
                vis[vi][vj] = true;
                d[vi][vj] = d[ui][uj] + 1;
                q.push(ii(vi, vj));
            }
        }
    }

    return false;
}

int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);

    cin>>n>>s;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin>>grid[i][j];
            if(grid[i][j] == 'M'){
                si = i;
                sj = j;
            }
            if(grid[i][j] == 'D'){
                fi = i;
                fj = j;
            }
        }
    }

    flood();

    //print();

    long long lo = 0, hi = 1000000000;
    while(lo < hi){
        long long mid = lo + (hi - lo + 1) / 2;
        if(check(mid)){
            lo = mid;
        }
        else{
            hi = mid - 1;
        }
    }

    if(!check(lo)) cout<<-1;
    else cout<<lo;


    return 0;
}

• Subtask 1: 84 / 100