Submission #103693

#	Time	Username	Problem	Language	Result	Execution time	Memory
103693		Badral	Mecho (IOI09_mecho)	C++17	10 / 100	512 ms	66560 KiB

mecho

#include<bits/stdc++.h>

using namespace std;

char a[1015][1015];
int bear[1105][1015];
int bee[1105][1015];
struct point{
    int x, y;
};
point mep(int a, int b) {point x; x.x = a; x.y = b; return x;}
int x = -1, y = -1;
int xxx = -1, yyy = -1;
    int n;
    int kk;
bool can(int k) {
    memset(bear, 0, sizeof bear);
    bear[x][y] = k*k;
    queue<point> q;
    q.push(mep(x, y));
    while(!q.empty()) {
        int x = q.front().x, y = q.front().y;
        q.pop();
        if( x < n && bear[x+1][y] == 0 && (a[x+1][y] == 'G' || a[x+1][y] == 'D') && bee[x+1][y] > (bear[x][y]+1)) {bear[x+1][y] = bear[x][y] + 1;q.push(mep(x+1, y));}
        if( x > 1 && bear[x-1][y] == 0 && (a[x-1][y] == 'G' || a[x-1][y] == 'D') && bee[x-1][y] > (bear[x][y]+1)) {bear[x-1][y] = bear[x][y] + 1;q.push(mep(x-1, y));}
        if( y < n && bear[x][y+1] == 0 && (a[x][y+1] == 'G' || a[x][y+1] == 'D') && bee[x][y+1] > (bear[x][y]+1)) {bear[x][y+1] = bear[x][y] + 1;q.push(mep(x, y+1));}
        if( y > 1 && bear[x][y-1] == 0 && (a[x][y-1] == 'G' || a[x][y-1] == 'D') && bee[x][y-1] > (bear[x][y]+1)) {bear[x][y-1] = bear[x][y] + 1;q.push(mep(x, y-1));}
    }
    // for(int i = 1; i <= n; i++) {
    //     for(int j = 1; j<= n; j++) {
    //         cout<<bear[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    return bear[xxx][yyy] != 0;  
}
int main() {
    cin >>n;
    cin >>kk;
    queue<point> p;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            bee[i][j] = INT_MAX; 
            cin >>a[i][j];
            if(a[i][j] == 'H') {p.push(mep(i, j));bee[i][j] = 0;}
            if(a[i][j] == 'M') {x = i; y = j;}
            if(a[i][j] == 'D') {xxx = i; yyy = j;}
        }
    }

    while(!p.empty()) {
        int x = p.front().x, y = p.front().y;
        p.pop();
        if(x < n && bee[x+1][y] > bee[x][y] + 1 && (a[x+1][y] != 'T' && a[x+1][y] != 'D')) {bee[x+1][y] = bee[x][y] + kk; p.push(mep(x+1, y));}
        if(x > 1 && bee[x-1][y] > bee[x][y] + 1 && (a[x-1][y] != 'T' && a[x-1][y] != 'D')) {bee[x-1][y] = bee[x][y] + kk; p.push(mep(x-1, y));}
        if(y < n && bee[x][y+1] > bee[x][y] + 1 && (a[x][y+1] != 'T' && a[x][y+1] != 'D')) {bee[x][y+1] = bee[x][y] + kk; p.push(mep(x, y+1));}
        if(y > 1 && bee[x][y-1] > bee[x][y] + 1 && (a[x][y-1] != 'T' && a[x][y-1] != 'D')) {bee[x][y-1] = bee[x][y] + kk; p.push(mep(x, y-1));}
    }
    // for(int i = 1; i <= n; i++) {
    //     for(int j = 1; j <= n; j++) {
    //         cout<<(bee[i][j] == INT_MAX ? -1 :bee[i][j])<<" ";
    //     }cout<<endl;
    // }
    int k = 0, mm = n * n;
    for(int i = mm/2; i >= 1; i /= 2) 
        while(i + k <= mm && can(i+k)) 
            k += i;
    cout<<(k == 0?-1:k);
}

• Subtask 1: 10 / 100