제출 #522413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522413		AndresTL	Mecho (IOI09_mecho)	C++11	100 / 100	216 ms	6212 KiB

mecho

// Problem: 10599. IOI 2009 - Mecho
// Contest: omegaUp
// URL: https://omegaup.com/arena/problem/IOI-2009-Mecho/?fromLogin=
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<utility>
#include<queue>
#include<string>
#define fi first
#define se second
using namespace std;
int n,s;
char mapa[802][802];
int colmena[802][802];
int mecho[802][802];
int mov[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool abeja(int i, int j){
	if(i<0 || i>n || j<0 || j>n) return 0;
	if(colmena[i][j]!=-1) return 0;
	if(mapa[i][j]=='T' || mapa[i][j]=='D') return 0;
	return 1;
}
void BFScolmena(){
	queue<pair<int,int>> q;
	pair<int,int> dad, son;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(mapa[i][j]=='H'){
				q.push(make_pair(i,j));
				colmena[i][j]=0;
			}	
		}
	}
	while(!q.empty()){
		dad=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			son=make_pair(dad.fi+mov[i][0],dad.se+mov[i][1]);
			if(!abeja(son.first,son.second))continue;
			colmena[son.fi][son.se]=colmena[dad.fi][dad.se]+1;
			q.push(son);
		}
	}
}
int i1,i2,j1,j2;
bool paso(int i,int j,int time){
	if(i<0 || i>n || j<0 || j>n) return 0;
	if(mecho[i][j]!=-1) return 0;
	if(mapa[i][j]=='T') return 0;
	if(mapa[i][j]=='D') return 1;
	if(time>=colmena[i][j]) return 0;
	return 1;
}
bool BFSmecho(int t){
	queue<pair<int,int>> q;
	pair<int,int>dad,son;
	int time;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			mecho[i][j]=-1;
		}
	}
	mecho[i1][j1]=0;
	if(t>=colmena[i1][j1]) return 0;
	q.push(make_pair(i1,j1));
	while(!q.empty()){
		dad=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			son=make_pair(dad.fi+mov[i][0],dad.se+mov[i][1]);
			time=t+(mecho[dad.fi][dad.se]+1)/s;
			if(!paso(son.fi,son.se,time)) continue;
			mecho[son.fi][son.se]=mecho[dad.fi][dad.se]+1;
			q.push(son);
		}
	}
	return mecho[i2][j2]!=-1;
}
int main(){
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			colmena[i][j]=-1;
			cin>>mapa[i][j];
			if(mapa[i][j]=='M'){i1=i;j1=j;}
			if(mapa[i][j]=='D'){i2=i;j2=j;}			
		}
	}
	BFScolmena();
	int l=0,r=n*n,m;
	int res=-1;
	while(l<=r){
		m =(l+r)/2;
		if(BFSmecho(m)){
			res=m;
			l=m+1;
		}else{
			r=m-1;
		}
	}
	cout<<res<<'\n';
}

• Subtask 1: 100 / 100