제출 #1281825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281825		Jawad_Akbar_JJ	Mecho (IOI09_mecho)	C++17	100 / 100	270 ms	6220 KiB

mecho

#include <iostream>
#include <queue>

using namespace std;
const int N = 800;
int n, s, M, D, seen2[N * N], seen1[N * N];
char a[N][N];
vector<int> hiv;
queue<int> Q1, Q2, dmy;

bool valid(int i, int j){
    return (i >= 0 and j >= 0 and i < n and j < n and a[i][j] != 'T');
}

void PushMecho(){
    queue<int> Nw;
    while (Q1.size() > 0){
        int cur = Q1.front();
        Q1.pop();
        int i = cur / n, j = cur % n;
        if (seen2[cur] == 1)
            continue;
        if (valid(i - 1, j) and seen2[cur - n] == 0 and seen1[cur - n] != 1)
            seen1[cur - n] = 1, Nw.push(cur - n);
        if (valid(i + 1, j) and seen2[cur + n] == 0 and seen1[cur + n] != 1)
            seen1[cur + n] = 1, Nw.push(cur + n);
        if (valid(i, j - 1) and seen2[cur - 1] == 0 and seen1[cur - 1] != 1)
            seen1[cur - 1] = 1, Nw.push(cur - 1);
        if (valid(i, j + 1) and seen2[cur + 1] == 0 and seen1[cur + 1] != 1)
            seen1[cur + 1] = 1, Nw.push(cur + 1);
    }
    swap(Q1, Nw);
}

void PushBee(){
    queue<int> Nw;
    while (Q2.size() > 0){
        int cur = Q2.front();
        Q2.pop();
        int i = cur / n, j = cur % n;
        
        if (valid(i - 1, j) and cur - n != D and seen2[cur - n] != 1)
            seen2[cur - n] = 1, Nw.push(cur - n);
        if (valid(i + 1, j) and cur + n != D and seen2[cur + n] != 1)
            seen2[cur + n] = 1, Nw.push(cur + n);
        if (valid(i, j - 1) and cur - 1 != D and seen2[cur - 1] != 1)
            seen2[cur - 1] = 1, Nw.push(cur - 1);
        if (valid(i, j + 1) and cur + 1 != D and seen2[cur + 1] != 1)
            seen2[cur + 1] = 1, Nw.push(cur + 1);
    }
    swap(Q2, Nw);
}

bool canHeReachAfter(int l){
    for (int i=0;i<n*n;i++)
        seen1[i] = seen2[i] = 0;
    Q1 = dmy, Q2 = dmy;

    for (int i : hiv)
        Q2.push(i), seen2[i] = 1;
    Q1.push(M), seen1[M] = 1;

    while (l > 0)
        PushBee(), l--;

    while (Q1.size() > 0){
        for (int i=0;i<s and Q1.size() > 0;i++)
            PushMecho();
        PushBee();
    }
    return seen1[D];
}

signed main(){
    cin>>n>>s;

    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            cin>>a[i][j];
            if (a[i][j] == 'M')
                M = i * n + j;
            if (a[i][j] == 'D')
                D = i * n + j;
            if (a[i][j] == 'H')
                hiv.push_back(i * n + j);
        }
    }

    int l = -1, r = n * n + 1;

    while (l + 1 < r){
        int mid = (l + r) / 2;
        if (canHeReachAfter(mid))
            l = mid;
        else
            r = mid;
    }
    cout<<l<<'\n';

}

• Subtask 1: 100 / 100