제출 #1071527

#제출 시각아이디문제언어결과실행 시간메모리
10715277againMecho (IOI09_mecho)C++17
0 / 100
494 ms15288 KiB
#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 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...