# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
633197 | czhang2718 | Mecho (IOI09_mecho) | C++17 | 184 ms | 6296 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |