Submission #898284

#	Time	Username	Problem	Language	Result	Execution time	Memory
898284		lalig777	Mecho (IOI09_mecho)	C++14	50 / 100	186 ms	9636 KiB

mecho

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int iini, ifin, jini, jfin, n, s;

bool way_home(int m, vector<vector<int> >&bemoment, vector<vector<char> >&grid){
	queue<pair<int,int> >mecho;
	vector<vector<pair<int,int> > >mechomoment(n, vector<pair<int,int> >(n, make_pair(1e9, 0)));
	mecho.push(make_pair(iini, jini));
	mechomoment[iini][jini]=make_pair(m, 1);
	while (!mecho.empty()){
		int i=mecho.front().first;
		int j=mecho.front().second;
		mecho.pop();
		int minut=mechomoment[i][j].first, steps=mechomoment[i][j].second;
		if (steps==s){
			minut++;
			steps=0;
		}steps++;
		if ((i!=0 && grid[i-1][j]=='D')||(j!=0 && grid[i][j-1]=='D')||(i!=n-1 && grid[i+1][j]=='D')||((j!=n-1 && grid[i][j+1]=='D'))){
			return true;
		}
		if (i!=0 and bemoment[i-1][j]>minut and mechomoment[i-1][j].first==1e9){
			mechomoment[i-1][j]=make_pair(minut, steps);
			mecho.push(make_pair(i-1, j));
		}if (j!=0 and bemoment[i][j-1]>minut and mechomoment[i][j-1].first==1e9){
			mechomoment[i][j-1]=make_pair(minut, steps);
			mecho.push(make_pair(i, j-1));
		}if (i!=n-1 and bemoment[i+1][j]>minut and mechomoment[i+1][j].first==1e9){
			mechomoment[i+1][j]=make_pair(minut, steps);
			mecho.push(make_pair(i+1, j));
		}if (j!=n-1 and bemoment[i][j+1]>minut and mechomoment[i][j+1].first==1e9){
			mechomoment[i][j+1]=make_pair(minut, steps);
			mecho.push(make_pair(i, j+1));
		}
	}return false;

}

int main(){
	cin>>n>>s;
	vector<vector<char> >grid(n, vector<char>(n));
	vector<vector<int> >bemoment(n, vector<int>(n, 1e9));
	queue<pair<int,int> >grassy;
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			cin>>grid[i][j];
			if (grid[i][j]=='H'){
				grassy.push(make_pair(i, j));
				bemoment[i][j]=0;
			}else if (grid[i][j]=='M'){
				iini=i;
				jini=j;
			}else if (grid[i][j]=='D'){
				ifin=i;
				jfin=j;
				bemoment[i][j]=-1;
			}else if (grid[i][j]=='T') bemoment[i][j]=-1;
		}
	}while (!grassy.empty()){
		int i=grassy.front().first;
		int j=grassy.front().second;
		grassy.pop();
		if (i!=0 and bemoment[i-1][j]==1e9){
			bemoment[i-1][j]=bemoment[i][j]+1;
			grassy.push(make_pair(i-1, j));
		}if (j!=0 and bemoment[i][j-1]==1e9){
			bemoment[i][j-1]=bemoment[i][j]+1;
			grassy.push(make_pair(i, j-1));
		}if (i!=n-1 and bemoment[i+1][j]==1e9){
			bemoment[i+1][j]=bemoment[i][j]+1;
			grassy.push(make_pair(i+1, j));
		}if (j!=n-1 and bemoment[i][j+1]==1e9){
			bemoment[i][j+1]=bemoment[i][j]+1;
			grassy.push(make_pair(i, j+1));
		}
	}int ans=-1;
	int l=0, r=bemoment[iini][ifin]-1, m;
	while (l<=r){
		m=(r-l)/2+l;
		if (l+1==r){
			if (way_home(r, bemoment, grid)){
				ans=r;
				l+=2;
			}else if (way_home(l, bemoment, grid)){
				ans=l;
				r-=2;
			}else ans=-1;
			break;
		}else if (l==r){
			if (way_home(r, bemoment, grid)){
				ans=r;
				l++;
			}else ans=-1;
			break;
		}
		if (way_home(m, bemoment, grid)) l=m;
		else r=m-1;
	}cout<<ans<<'\n';
	return 0;
}

• Subtask 1: 50 / 100