Submission #682821

#	Time	Username	Problem	Language	Result	Execution time	Memory
682821		NONTAC	Mecho (IOI09_mecho)	C++11	46 / 100	239 ms	6920 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};
int n, s;
int si, sj, fi, fj;
char grid[802][802];
int 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(int k)
{
    INIT();
    d[si][sj] = k * s;
    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 && uj == fj){
            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]){
                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();
    reach[fi][fj] = INT_MAX;

    //print();

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

    if(lo == 0) cout<<-1;
    else cout<<lo - 1;


    return 0;
}

• Subtask 1: 46 / 100