제출 #879152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
879152		anarch_y	Mecho (IOI09_mecho)	C++17	10 / 100	151 ms	7004 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) begin(x), end(x)
#define pb push_back

int N, S;
char A[800][800];
int d[800][800], D[800][800];
pii M, P;
int ans = -1;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

bool invalid(int r, int c){
    if(r<0 or r>=N or c<0 or c>=N) return true;
    if(A[r][c] == 'T') return true;
    return false;
}

bool check(int k){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++) d[i][j] = 1e9;
    }
    queue<pii> q, qn;
    q.push(M);
    int tt = 0;
    d[M.first][M.second] = 0;
    bool found = false;
    for(int x=0; x<N; x++){
        while(!q.empty()){
            auto p = q.front(); q.pop();
            int r = p.first, c = p.second;
            if(d[r][c] == (tt+1)*S){
                if(D[r][c]>k+tt+1){
                    qn.push({r, c});
                }
                continue;
            }
            for(int i=0; i<4; i++){
                int nr = r+dr[i], nc = c+dc[i];
                if(invalid(nr, nc)) continue;
                if(d[nr][nc] != 1e9) continue;
                d[nr][nc] = d[r][c]+1;
                q.push({nr, nc});
                if(P == pii(nr, nc)) found = true;
            }
        }
        if(found) break;
        q = qn;
        qn = queue<pii>();
        tt++;
    }
    return found;
}

void solve(){
    int L = 1, R = N;
    while(L <= R){
        int mid = (L+R)/2;
        if(check(mid)){
            ans = mid;
            L=mid+1;
        }
        else R=mid-1;
    }
}

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

    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, j};
            if(A[i][j] == 'D') P = {i, j};
            d[i][j] = D[i][j] = 1e9;
        }
    }
    queue<pii> Q;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(A[i][j] == 'H'){
                Q.push({i, j});
                D[i][j] = 0;
            }
        }
    }

    while(!Q.empty()){
        auto p = Q.front(); Q.pop();
        int r = p.first, c = p.second;
        for(int i=0; i<4; i++){
            int nr = r+dr[i], nc = c+dc[i];
            if(invalid(nr, nc)) continue;
            if(A[nr][nc] == 'D') continue;
            if(D[nr][nc] != 1e9) continue;
            D[nr][nc] = D[r][c]+1;
            Q.push({nr, nc});
        }
    }
    solve();
    cout << ans;

}

• Subtask 1: 10 / 100