제출 #1175799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175799		lnwrice	Mecho (IOI09_mecho)	C++20	84 / 100	246 ms	7800 KiB

mecho

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
using namespace std;

#define INT long long
#define MAX_INT 2000000024

struct RICE {
    int x;
    int y;
    int t;
};

string str;
vector<vector<int>> b, bear;
vector<string> arr;
queue<struct RICE> q;
int n, m;

void show_b() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(b[i][j] == MAX_INT) {
                cout << "-1 ";
                continue;
            }
            cout << b[i][j] << " ";
        }   
        cout << endl;
    }
}
void show_bear() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(bear[i][j] == MAX_INT) {
                cout << "-1 ";
                continue;
            }
            cout << bear[i][j] << " ";
        }   
        cout << endl;
    }
}

int in_map(int x, int y) {
    if(x >= 0 && x < n && y >= 0 && y < n) return 1;
    return 0;
}
void q_add(int x, int y, int t) {
    if(!in_map(x, y)) return;
    q.push({x, y, t});
}

void q_action(int x, int y, int t) {
    if(!in_map(x, y)) return;
    if(arr[x][y] != 'G' && arr[x][y] != 'H') return;
    if(b[x][y] > t) b[x][y] = t;
    else return;
    q_add(x+1, y, t + m);
    q_add(x-1, y, t + m);
    q_add(x, y+1, t + m);
    q_add(x, y-1, t + m);
}

void run(int x, int y, int t) {
    if(!in_map(x, y)) return;
    q.push({x, y, t});
}
void run_action(int x, int y, int t) {
    if(!in_map(x, y)) return;
    if(arr[x][y] != 'G' && arr[x][y] != 'M' && arr[x][y] != 'D') return;
    if(bear[x][y] > t) bear[x][y] = t;
    else return;
    if(bear[x][y] >= b[x][y]) return;
    run(x+1, y, t+1);
    run(x-1, y, t+1);
    run(x, y+1, t+1);
    run(x, y-1, t+1);
}

void clear_bear() {
    int i, j;
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            bear[i][j] = MAX_INT;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);

    int i, j, k, x, y, tx, ty;
    cin >> n >> m;
    arr.resize(n+2);
    //for(auto& num : arr) num.resize(n+2);
    b.resize(n+2);
    for(auto& num : b) {
        num.resize(n+2);
        for(auto& num2 : num) {
            num2 = MAX_INT;
        }
    }
    bear.resize(n+2);
    for(auto& num : bear) {
        num.resize(n+2);
    }
    
    for(i = 0; i < n; i++) {
        cin >> arr[i];
        for(j = 0; j < n; j++) {
            if(arr[i][j] == 'H') {
                q.push({i, j, 0});
            }
            else if(arr[i][j] == 'M') {
                x = i;
                y = j;
            }
            else if(arr[i][j] == 'D') {
                tx = i;
                ty = j;
            }
        }
    }

    while(!q.empty()) {
        q_action(q.front().x, q.front().y, q.front().t);
        q.pop();
    }

    //show_b();
    //return 0;

    int start, mid, end, ans = -1;
    for(start = 0, end = n*n; start <= end; ) {
        mid = (start + end)/2;
        clear_bear();
        q.push({x, y, mid * m});
        while(!q.empty()) {
            run_action(q.front().x, q.front().y, q.front().t);
            q.pop();
        }
        //show_bear();
        if(bear[tx][ty] == MAX_INT) {
            end = mid-1;
        }
        else {
            start = mid+1;
            ans = max(ans, mid);
        }
    }

    cout << ans;
    
    return 0;
}

• Subtask 1: 84 / 100