제출 #633197

#제출 시각아이디문제언어결과실행 시간메모리
633197czhang2718Mecho (IOI09_mecho)C++17
100 / 100
184 ms6296 KiB
#include<bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i=a; i<=b; i++) #define all(x) x.begin(), x.end() #define sz(x) (int) x.size() #define pb push_back #define f first #define s second #define nl '\n' typedef long long ll; // #define int ll typedef vector<int> vi; typedef pair<int, int> pii; #define nl '\n' const int N=800; int n, s; string grid[N]; int bee[N][N]; int dist[N][N]; bool block[N][N]; int dx[]={0, 0, 1, -1}; int dy[]={1, -1, 0, 0}; signed main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> s; for(int i=0; i<n; i++){ cin >> grid[i]; } auto check=[&](int t)->bool{ queue<pair<int,int>> q; rep(i,0,n-1) rep(j,0,n-1){ if(grid[i][j]=='M'){ if(bee[i][j]<=t) return 0; q.push({i,j}); dist[i][j]=0; } else dist[i][j]=1e9; } while(!q.empty()){ pair<int,int> p=q.front(); q.pop(); int x=p.first, y=p.second; if(grid[x][y]=='D') return 1; // cout << x << y << '\n'; for(int k=0; k<4; k++){ int nx=x+dx[k]; int ny=y+dy[k]; if(nx<0 || nx==n || ny<0 || ny==n || grid[nx][ny]=='T' || dist[nx][ny]!=1e9) continue; if(bee[nx][ny]>t+(dist[x][y]+1)/s){ dist[nx][ny]=dist[x][y]+1; q.push({nx,ny}); } } } return 0; }; queue<pair<int,int>> q; rep(i,0,n-1) rep(j,0,n-1){ if(grid[i][j]=='H') q.push({i,j}), bee[i][j]=0; else bee[i][j]=1e9; } while(!q.empty()){ pair<int,int> p=q.front(); int x=p.first, y=p.second; q.pop(); for(int k=0; k<4; k++){ int nx=x+dx[k]; int ny=y+dy[k]; if(nx<0 || nx==n || ny<0 || ny==n || grid[nx][ny]=='T' || grid[nx][ny]=='D' || bee[nx][ny]!=1e9) continue; bee[nx][ny]=bee[x][y]+1; q.push({nx,ny}); } } // rep(i,0,n-1){ // rep(j,0,n-1){ // cout << bee[i][j] << " "; // } // cout << nl; // } int x=0; for(int i=20; i>=0; i--){ if(check(x+(1<<i))) x+=(1<<i); } cout << (check(x)?x:-1); // rep(i,1,1) cout << check(i) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...