제출 #978627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978627		Bodisha	Mecho (IOI09_mecho)	C++17	81 / 100	1078 ms	7544 KiB

mecho

#include <bits/stdc++.h>
#define MAX_N 801

using namespace std;

int n, s;
char grid[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int beed[MAX_N][MAX_N];
int steps[MAX_N][MAX_N];

bool check(int t) {
    pair<int, int> mecho_pos, home_pos;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            visited[i][j] = false;
            if(grid[i][j] == 'M') {
                mecho_pos = {i, j};
            }
            if(grid[i][j] == 'D') {
                home_pos = {i, j};
            }
        }
    }
    if(t >= beed[mecho_pos.first][mecho_pos.second]) {
        return false;
    }
    queue<pair<pair<int, int>, int>> newq;
    visited[mecho_pos.first][mecho_pos.second] = true;
    newq.push({mecho_pos, 0});
    while(!newq.empty()) {
        pair<pair<int, int>, int> curr = newq.front(); 
        newq.pop();
        int tmp = t + 1 + ((curr.second + 1) / s);
        if(curr.first.first + 1 < n && tmp <= beed[curr.first.first + 1][curr.first.second] && !visited[curr.first.first + 1][curr.first.second] && (grid[curr.first.first + 1][curr.first.second] == 'G' || grid[curr.first.first + 1][curr.first.second] == 'M')) {
            visited[curr.first.first + 1][curr.first.second] = true;
            newq.push({{curr.first.first + 1, curr.first.second}, curr.second + 1});
        }
        if(curr.first.first - 1 >= 0 && tmp <= beed[curr.first.first - 1][curr.first.second] && !visited[curr.first.first - 1][curr.second] && (grid[curr.first.first - 1][curr.first.second] == 'G' || grid[curr.first.first - 1][curr.first.second] == 'M')) {
            visited[curr.first.first - 1][curr.first.second] = true;
            newq.push({{curr.first.first - 1, curr.first.second}, curr.second + 1});
        }
        if(curr.first.second + 1 < n && tmp <= beed[curr.first.first][curr.first.second + 1] && !visited[curr.first.first][curr.first.second + 1] && (grid[curr.first.first][curr.first.second + 1] == 'G' || grid[curr.first.first][curr.first.second + 1] == 'M')) {
            visited[curr.first.first][curr.first.second + 1] = true;
            newq.push({{curr.first.first, curr.first.second + 1}, curr.second + 1});
        }
        if(curr.first.second - 1 >= 0 && tmp <= beed[curr.first.first][curr.first.second - 1] && !visited[curr.first.first][curr.first.second - 1] && (grid[curr.first.first][curr.first.second - 1] == 'G' || grid[curr.first.first][curr.first.second - 1] == 'M')) {
            visited[curr.first.first][curr.first.second - 1] = true;
            newq.push({{curr.first.first, curr.first.second - 1}, curr.second + 1});
        }
    }
    if(home_pos.first + 1 < n && visited[home_pos.first + 1][home_pos.second]) {
        return true;
    }
    if(home_pos.first - 1 >= 0 && visited[home_pos.first - 1][home_pos.second]) {
        return true;
    }
    if(home_pos.second + 1 < n && visited[home_pos.first][home_pos.second + 1]) {
        return true;
    }
    if(home_pos.second - 1 >= 0 && visited[home_pos.first][home_pos.second - 1]) {
        return true;
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    vector<pair<int, int>> hives;
    pair<int, int> mecho_pos;
    cin >> n >> s;
    for(int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        for(int j = 0; j < n; j++) {
            grid[i][j] = tmp[j];
            if(grid[i][j] == 'H') {
                hives.push_back({i, j});
            }
            if(grid[i][j] == 'M') {
                mecho_pos = {i, j};
            }
        }
    }
    queue<pair<int, int>> q;
    visited[mecho_pos.first][mecho_pos.second] = true;
    steps[mecho_pos.first][mecho_pos.second] = 0;
    q.push(mecho_pos);
    while(!q.empty()) {
        pair<int, int> curr = q.front(); 
        q.pop();
        if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M')) {
            visited[curr.first + 1][curr.second] = true;
            steps[curr.first + 1][curr.second] = steps[curr.first][curr.second] + 1;
            q.push({curr.first + 1, curr.second});
        }
        if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M')) {
            visited[curr.first - 1][curr.second] = true;
            steps[curr.first - 1][curr.second] = steps[curr.first][curr.second] + 1;
            q.push({curr.first - 1, curr.second});
        }
        if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M')) {
            visited[curr.first][curr.second + 1] = true;
            steps[curr.first][curr.second + 1] = steps[curr.first][curr.second] + 1;
            q.push({curr.first, curr.second + 1});
        }
        if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M')) {
            visited[curr.first][curr.second - 1] = true;
            steps[curr.first][curr.second - 1] = steps[curr.first][curr.second] + 1;
            q.push({curr.first, curr.second - 1});
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            visited[i][j] = false;
        }
    }
    for(auto iter : hives) {
        visited[iter.first][iter.second] = true;
        beed[iter.first][iter.second] = 0;
        q.push(iter);
    }
    while(!q.empty()) {
        pair<int, int> curr = q.front(); 
        q.pop();
        if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M')) {
            visited[curr.first + 1][curr.second] = true;
            beed[curr.first + 1][curr.second] = beed[curr.first][curr.second] + 1;
            q.push({curr.first + 1, curr.second});
        }
        if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M')) {
            visited[curr.first - 1][curr.second] = true;
            beed[curr.first - 1][curr.second] = beed[curr.first][curr.second] + 1;
            q.push({curr.first - 1, curr.second});
        }
        if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M')) {
            visited[curr.first][curr.second + 1] = true;
            beed[curr.first][curr.second + 1] = beed[curr.first][curr.second] + 1;
            q.push({curr.first, curr.second + 1});
        }
        if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M')) {
            visited[curr.first][curr.second - 1] = true;
            beed[curr.first][curr.second - 1] = beed[curr.first][curr.second] + 1;
            q.push({curr.first, curr.second - 1});
        }
    }
    int l = 0, r = n * n;
    int ans = -1;
    // true true true ... (true) false false
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 81 / 100