제출 #1312291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312291		klalnwza007	Mecho (IOI09_mecho)	C++17	4 / 100	34 ms	7700 KiB

mecho

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

int bee[810][810];
bool visbee[810][810];
int mhee[810][810];
bool vismhee[810][810];
string grid[810];

typedef pair<int,int> pii;
int di[] = {0,0,1,-1};
int dj[] = {1,-1,0,0};

queue<pii> q,b;
pii home;

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,s; cin >> n >> s;

    for (int i=0;i<n;i++) {
        cin >> grid[i];
        for (int j=0;j<n;j++) {
            if (grid[i][j] == 'H') {
                b.emplace(i,j);
                bee[i][j] = 0;
                visbee[i][j] = true;
            }
            if (grid[i][j] == 'M') {
                q.emplace(i,j);
                mhee[i][j] = 0;
                vismhee[i][j] = true;
            }
        }
    }

    while (!b.empty()) {
        auto [i,j] = b.front();
        b.pop();

        for (int k=0;k<4;k++) {
            int ni = i + di[k];
            int nj = j + dj[k];

            if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            if (visbee[ni][nj]) continue;
            if (grid[ni][nj] == 'D' || grid[ni][nj] == 'T') continue;

            bee[ni][nj] = bee[i][j] + 1;
            visbee[ni][nj] = true;
            b.emplace(ni,nj);
        }

    }
    while (!q.empty()) {
        auto [i,j] = q.front();
        q.pop();

        for (int k=0;k<4;k++) {
            int ni = i + di[k];
            int nj = j + dj[k];

            if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            if (vismhee[ni][nj]) continue;
            if (grid[ni][nj] == 'T' || (visbee[ni][nj] && bee[ni][nj] <= ((mhee[i][j]+1)/s))) continue;

            mhee[ni][nj] = mhee[i][j] + 1;

            if (grid[ni][nj] == 'D') {
                home = {ni,nj};
                vismhee[ni][nj] = true;
                while (!q.empty()) q.pop();
                break;
            }
            vismhee[ni][nj] = true;
            q.emplace(ni,nj);

        }
    }
    auto[i,j] = home;
    cout << bee[i][j] - (mhee[i][j]/s)-1;


}

• Subtask 1: 4 / 100