제출 #1071527

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071527		7again	Mecho (IOI09_mecho)	C++17	0 / 100	494 ms	15288 KiB

mecho

#include <bits/stdc++.h>

using namespace std ;

const int N = 1001 ;
int dx[]{0 , 0 , 1 , -1} ;
int dy[]{1 , -1 , 0 , 0} ;


int n , s ;
pair <int , int> Honey , Home ;
char a[N][N] ;
bool is[N][N] ;
bool inside(int x , int y) {
    return (x >= 0 && y >= 0 && x < n && y < n && a[x][y] != 'T') ;
}

int ok(int time) {

    fill_n(&is[0][0] , N * N , false ) ;

    int mn2[n][n] ;
    fill_n(&mn2[0][0] , n*n , 1e9) ;
    queue<pair <int , int>>  q2 ;
    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < n ; j++) {
            if(a[i][j] == 'H') {
                q2.push({i, j}) ;
                is[i][j] = true ;
                mn2[i][j] = 0 ;
            }
        }
    }
    while(q2.size()) {
        pair <int , int> t = q2.front() ;
        q2.pop() ;
        for(int i = 0 ; i < 4 ; i++) {
            int x = t.first + dx[i] ;
            int y = t.second + dy[i] ;
            if(inside(x , y) &&  mn2[t.first][t.second] + 1 < mn2[x][y] && mn2[t.first][t.second] + 1 < time) {
                is[x][y] = true ;
                mn2[x][y] = mn2[t.first][t.second] + 1 ;
                q2.push({x, y}) ;
            }
        }
    }
    // for(int i = 0 ; i < n ; i++) {
    //     for(int j = 0 ; j < n ; j++) {
    //         cout << is[i][j] << " " ;
    //     }
    //     cout << endl ;
    // }
    int mn[n][n] ;
    fill_n(&mn[0][0] , n * n , 1e9 ) ;
    queue <pair <int , int>> q ;
    mn[Honey.first][Honey.second] = 0 ;
    if(!is[Honey.first][Honey.second])
        q.push(Honey) ;
    while(!q.empty()) {
        pair <int , int> t = q.front() ;
        q.pop() ;
        for(int i = 0 ; i < 4 ; i++) {
            int x = t.first + dx[i] ;
            int y = t.second + dy[i] ;
            if(is[x][y] == false && inside(x , y) && mn[t.first][t.second] + 1 < mn[x][y]) {
                mn[x][y] = mn[t.first][t.second] + 1 ;
                q.push({x , y}) ;
            }
        }
    }
    // for(int i = 0 ; i < n ; i++) {
    //     for(int j = 0 ; j < n ; j++) {
    //         cout << mn[i][j] << " " ;
    //     }
    //     cout << endl ;
    // }
    if(mn[Home.first][Home.second] == 1e9)
        return  -1 ;
    int req = (mn[Home.first][Home.second] / time) + (mn[Home.first][Home.second] % time != 0) ;
    return time - req ;
}
int main() {
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    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')
                Honey = {i , j} ;
            if(a[i][j] == 'D')
                Home = {i , j} ;
        }
    }

    int l = 0 , r = 1e9 ;
    while(l + 1 < r) {
        int m = l + (r - l) / 2 ;
        if(ok(m) >= 0)
            l = m ;
        else
            r = m ;
    }
    cout << ok(l) << endl ;
}

• Subtask 1: 0 / 100