제출 #953266

#제출 시각아이디문제언어결과실행 시간메모리
953266dpsaveslivesMecho (IOI09_mecho)C++17
29 / 100
146 ms9016 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; const int MAXN = 810; char grid[MAXN][MAXN]; int dr[4] = {0,0,1,-1}, dc[4] = {1,-1,0,0},N; bool goodbees(int r, int c){ return r >= 0 && c >= 0 && r <= N-1 && c <= N-1 && grid[r][c] != 'T' && grid[r][c] != 'D'; } bool goodmecho(int r, int c){ return r >= 0 && c >= 0 && r <= N-1 && c <= N-1 && grid[r][c] != 'T'; } const int INF = 1e9; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int S; cin >> N >> S; queue<pair<int,int>> q; vector<vector<int>> dist(N,vector<int>(N,INF)); pair<int,int> m,home; for(int i = 0;i<N;++i){ for(int j = 0;j<N;++j){ cin >> grid[i][j]; if(grid[i][j] == 'H'){ q.push({i,j}); dist[i][j] = 0; } else if(grid[i][j] == 'M'){ m.f = i, m.s = j; } else if(grid[i][j] == 'D'){ home.f = i, home.s = j; } } } while(!q.empty()){ int r = q.front().f, c = q.front().s; q.pop(); for(int i = 0;i<4;++i){ int nr = r+dr[i], nc = c+dc[i]; if(goodbees(nr,nc)){ if(dist[nr][nc] > dist[r][c]+1){ dist[nr][nc] = dist[r][c]+1; q.push({nr,nc}); } } } } /*vector<vector<int>> mecho(N,vector<int>(N,INF)); mecho[m.f][m.s] = 0; q.push(m); while(!q.empty()){ int r = q.front().f, c = q.front().s; q.pop(); for(int i = 0;i<4;++i){ int nr = r+dr[i], nc = c+dc[i]; if(goodmecho(nr,nc)){ if(mecho[nr][nc] > mecho[r][c]+1){ mecho[nr][nc] = mecho[r][c]+1; q.push({nr,nc}); } } } }*/ int lo = 0, hi = INF; if(hi < 0){ cout << "-1\n"; return 0; } vector<vector<int>> D(N,vector<int>(N,INF)); while(lo < hi){ int mid = lo+(hi-lo+1)/2; //time //cout << mid << "\n"; D = vector<vector<int>>(N,vector<int>(N,INF)); q.push(m); D[m.f][m.s] = 0; while(!q.empty()){ int r = q.front().f, c = q.front().s; q.pop(); //cout << r << " " << c << "\n"; for(int i = 0;i<4;++i){ int nr = r+dr[i], nc = c+dc[i]; if(goodmecho(nr,nc)){ if(D[r][c]/S +mid < dist[nr][nc] && D[r][c]+1 < D[nr][nc]){ D[nr][nc] = D[r][c]+1; q.push({nr,nc}); } } } } if(D[home.f][home.s] == INF){ hi = mid-1; } else{ lo = mid; } } cout << lo << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...