# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
583474 | HeyYouNotYouYou | Mecho (IOI09_mecho) | C++14 | 270 ms | 16572 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 801,INF=1e12;
int n , o, srcx, srcy, destx, desty, ar[N][N],arr[N][N],arr2[N][N];
int dx[4]={0,-1,1,0};
int dy[4]={-1,0,0,1};
bool vis[N][N];
bool valid(int x, int y){
if(x>=0 && x<n && y>=0 && y<n) return true;
return false;
}
bool check(int mins)
{
memset(vis,0,sizeof vis);
memset(arr2,0,sizeof arr2);
queue<pair<int,int>>qq;
qq.push({srcx,srcy});
vis[srcx][srcy]=1;
if(arr[srcx][srcy]<=mins) return false;
arr2[srcx][srcy]=0;
while(!qq.empty()){
int curx=qq.front().first;
int cury=qq.front().second;
qq.pop();
for(int i = 0 ; i < 4; i ++)
{
int gox = curx+dx[i], goy = cury+dy[i];
if(valid(gox,goy) && !vis[gox][goy] && ar[gox][goy]!=-1){
if(arr[gox][goy] > floor((double)(arr2[curx][cury]+1)/(double)o)+mins){
// cout<<curx<<" "<<cury<<" "<<gox<<" "<<goy<<" "<<arr2[curx][cury]<<" "<<arr[gox][goy]-mins<<" "<<c<<" "<<arr2[curx][cury]+(c%o==0&&c>0)<<endl;
vis[gox][goy]=1;
arr2[gox][goy]=arr2[curx][cury]+1;
if(gox==destx&&goy==desty) return true;
qq.push({gox,goy});
}
}
}
}
return false;
}
void bfs(){
queue<pair<int,int>>q;
memset(vis,0,sizeof vis);
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < n ; j ++)
{
if(ar[i][j]==1){
q.push({i,j});
vis[i][j]=1;
arr[i][j]=0;
}
}
while(!q.empty())
{
int curx=q.front().first;
int cury=q.front().second;
q.pop();
for(int i = 0 ; i < 4; i ++)
{
int gox = curx+dx[i], goy = cury+dy[i];
if(valid(gox,goy) && !vis[gox][goy] && ar[gox][goy]!=-1 && (destx!=gox || desty!=goy)){
vis[gox][goy]=1;
arr[gox][goy]=arr[curx][cury]+1;
q.push({gox,goy});
}
}
}
}
int32_t main()
{
//freopen("abc.in", "r", stdin);
cin >> n >> o;
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j ++){
char x; cin >> x;
arr[i][j]=1e9;
ar[i][j] = (x=='H'?1:((x=='G'||x=='D'||x=='M')?0:-1));
if(x=='M') srcx=i, srcy=j;
if(x=='D') destx=i, desty=j;
}
}
bfs();
int l = 0 , r = 1e9;
int ans=-1;
while(l <= r)
{
int mid = l + (r - l) / 2;;
// cout<<mid<<endl;
if(check(mid))
{
l = mid+1;
ans=mid;
}
else
{
r = mid-1;
}
}
cout<<ans<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |