Submission #522409

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
522409	2022-02-04T22:51:33 Z	AndresTL	Mecho (IOI09_mecho)	C++11	Compilation error	0 ms	0 KB

mecho

#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';

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:97:17: error: expected '}' at end of input
   97 |  cout<<res<<'\n';
      |                 ^
mecho.cpp:75:11: note: to match this '{'
   75 | int main(){
      |           ^