제출 #1143010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143010		poltanos	Mecho (IOI09_mecho)	C++20	58 / 100	751 ms	24780 KiB

mecho

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

const vector<int> dx {1, -1, 0, 0};
const vector<int> dy {0, 0, 1, -1};

int n, s;
vector<string> grid(1000);
vector<vector<int>> bee_time(1000, vector<int> (1000, 1e18));
vector<vector<int>> mecho_time(1000, vector<int> (1000, 1e18));

bool inside(int x, int y, bool is_mecho, int time = 0){

    bool is_inside = (x > -1 && x < n && y > -1 && y < n && grid[x][y] != 'T');
    if(!is_inside) return false;

    if(is_mecho) is_inside = is_mecho && bee_time[x][y] > time;
    return is_inside;
}

void calculate_bee_time(int x, int y){
    queue<pair<int, int>> q;
    q.push({x, y});
    bee_time[x][y] = 0;

    while(!q.empty()){
        auto [curr_x, curr_y] = q.front();
        q.pop();

        for(int i = 0; i < 4; i++){
            int new_x = curr_x + dx[i], new_y = curr_y + dy[i];

            if(inside(new_x, new_y, false) && bee_time[new_x][new_y] > bee_time[curr_x][curr_y] + 1){
                bee_time[new_x][new_y] = bee_time[curr_x][curr_y] + 1;
                q.push({new_x, new_y});
            }
        }
    }
}

void solve(){
    cin >> n >> s;

    for(int i = 0; i < n; i++) cin >> grid[i];

    int sx, sy, ex, ey;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(grid[i][j] == 'H'){
                calculate_bee_time(i, j);
            }

            if(grid[i][j] == 'M') sx = i, sy = j;
            if(grid[i][j] == 'D') ex = i, ey = j;
        }
    }


    int lo = 0, hi = 1e9;
    while(lo < hi){
        int mid = (lo + hi + 1)/2;

        mecho_time = vector<vector<int>> (1000, vector<int> (1000, 1e18));
        mecho_time[sx][sy] = mid;
        queue<array<int, 4>> q; // { x, y, time, step # }
        q.push({sx, sy, mid, 0});

        while(!q.empty()){
            auto [curr_x, curr_y, time, step_count] = q.front();
            q.pop();


            if(++step_count >= s){
                time++;
                step_count = 0;
            }

            for(int i = 0; i < 4; i++){
                int new_x = curr_x + dx[i], new_y = curr_y + dy[i];
                //cout << new_x << " , " << new_y << endl;
                //cout << boolalpha << inside(new_x, new_y, true, time) << endl;

                if(inside(new_x, new_y, true, time) && mecho_time[new_x][new_y] > time){
                    mecho_time[new_x][new_y] = time;
                    q.push({new_x, new_y, time, step_count});
                }
            }
        }
        //cout << "NO EROR" << endl;

        if(mecho_time[ex][ey] != 1e18){
            lo = mid;
        }else{
            hi = mid - 1;
        }
    }

    if(hi == 0){
        cout << -1 << endl;
        return;
    }

    cout << lo << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    while(t--) solve();

    return 0;
}

• Subtask 1: 58 / 100