제출 #578682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578682		a_aguilo	Mecho (IOI09_mecho)	C++14	38 / 100	244 ms	6232 KiB

mecho

#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

typedef vector<char> vc;
typedef vector<vc> vvc;

int INF = 1e9;
int n, s;

vvi FloodFill (vector<pair<int, int>>& V, vvc& CharMap){
    vvi ans(n, vi(n, INF));
    queue<pair<int, int>> Q;
    for(pair<int, int> start : V){
        Q.push(start);
        ans[start.first][start.second] = 0;
    }
    while(!Q.empty()){
        pair<int, int> act = Q.front(); Q.pop();
        int Xact = act.first;
        int Yact = act.second;
        if(Xact > 0 and ans[Xact-1][Yact] == INF and CharMap[Xact-1][Yact] == 'G'){
            ans[Xact-1][Yact] = ans[Xact][Yact]+1;
            Q.push(make_pair(Xact-1, Yact));
        }
        if (Yact > 0 and ans[Xact][Yact-1]== INF and CharMap[Xact][Yact-1] == 'G'){
            ans[Xact][Yact-1] = ans[Xact][Yact]+1;
            Q.push(make_pair(Xact, Yact-1));
        }
        if(Xact < (n-1) and ans[Xact+1][Yact] == INF and CharMap[Xact+1][Yact] == 'G'){
            ans[Xact+1][Yact] = ans[Xact][Yact]+1;
            Q.push(make_pair(Xact+1, Yact));
        }
        if(Yact < (n-1) and ans[Xact][Yact+1] == INF and CharMap[Xact][Yact+1] == 'G'){
            ans[Xact][Yact+1] = ans[Xact][Yact]+1;
            Q.push(make_pair(Xact, Yact+1));
        }
    }
    return ans;
}

bool bfsMecho (pair<int, int> StartPos, int initialTime, vvi& listaAdy, vvc& CharMap){
    vvi visited (n, vi(n, 0));
    visited[StartPos.first][StartPos.second] = 1;
    queue<pair<int, pair<int, int>>> Q;
    Q.push(make_pair(initialTime*s, StartPos));
    while(!Q.empty()){
        pair<int, pair<int, int>> act = Q.front(); Q.pop();
        int PasosAct = act.first;
        int MinuteAct = PasosAct/s;
        int x = act.second.first;
        int y = act.second.second;

        if(CharMap[x][y] == 'D') return true;

        if(x > 0 and MinuteAct < listaAdy[x-1][y] and (CharMap[x-1][y] == 'G' or CharMap[x-1][y] == 'D') and !visited[x-1][y] ){
            Q.push(make_pair(PasosAct+1, make_pair(x-1, y)));
            visited[x-1][y] = 1;
        }
        if(y > 0 and MinuteAct < listaAdy[x][y-1] and (CharMap[x][y-1] == 'G' or CharMap[x][y-1] == 'D') and !visited[x][y-1]){
            Q.push(make_pair(PasosAct+1, make_pair(x, y-1)));
            visited[x][y-1] = 1;
        }
        if(x < (n-1) and MinuteAct < listaAdy[x+1][y] and (CharMap[x+1][y] == 'G' or CharMap[x+1][y] == 'D') and !visited[x+1][y]){
            Q.push(make_pair(PasosAct+1, make_pair(x+1, y)));
            visited[x+1][y] = 1;
        }
        if(y < (n-1) and MinuteAct < listaAdy[x][y+1] and (CharMap[x][y+1] == 'G' or CharMap[x][y+1] == 'D') and !visited[x][y+1] ){
            Q.push(make_pair(PasosAct+1, make_pair(x, y+1)));
            visited[x][y+1] = 1;
        }
    }
    return false;
}

int main(){
    char c;
    cin >> n >> s;
    vector<pair<int, int>> IniciosAbejas;
    pair<int, int> InicioMecho;
    vvc mapa(n, vc(n));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> c;
            //T = tree --> no one can pass
            //M = mecho initially
            //D = target
            //G = grass
            //H = hive
            if(c == 'M') InicioMecho = make_pair(i, j);
            else if (c == 'H') IniciosAbejas.push_back(make_pair(i, j));
            mapa[i][j] = c;
        }
    }
    vvi Matrix = FloodFill(IniciosAbejas, mapa);

    int hi = n*n;
    int lo = 0;
    while(hi >= lo){
        int mid = lo + (hi-lo)/2;
        if(bfsMecho(InicioMecho, mid, Matrix, mapa)) lo = mid+1;
        else hi = mid-1;
    }
    if(hi < 0 and !bfsMecho(InicioMecho, 0, Matrix, mapa)) cout << -1 << endl;
    else if (hi < 0) cout << 0;
    else cout << hi << endl;

    /*
    for(int i = 0; i < n; ++i){
        cout << Matrix[i][0];
        for(int j = 1; j < n; ++j){
            cout << " " << Matrix[i][j];
        }
        cout << endl;
    }*/

    return 0;
}

• Subtask 1: 38 / 100