Submission #1219625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219625		boclobanchat	Mecho (IOI09_mecho)	C++20	100 / 100	123 ms	6980 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
const int INF=1e9;
int F[888][888],G[888][888];
string s[888];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    int x1,y1,x2,y2;
    queue< pair<int,int> > Q;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) F[i][j]=INF;
    for(int i=1;i<=n;i++)
    {
    	cin>>s[i];
    	s[i]=' '+s[i];
    	for(int j=1;j<=n;j++) if(s[i][j]=='H') F[i][j]=0,Q.push({i,j});
    	else if(s[i][j]=='M') x1=i,y1=j;
    	else if(s[i][j]=='D') x2=i,y2=j;
	}
	while(!Q.empty())
	{
		int a=Q.front().first,b=Q.front().second;
		Q.pop();
		for(int i=0;i<4;i++)
		{
			int x=a+dx[i],y=b+dy[i];
			if(min(x,y)>=1&&max(x,y)<=n&&s[x][y]!='T'&&s[x][y]!='D'&&F[x][y]==INF) F[x][y]=F[a][b]+1,Q.push({x,y});
		}
	}
	int l=0,r=F[x1][y1]-1,ans=-1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) G[i][j]=INF;
		G[x1][y1]=mid*k,Q.push({x1,y1});
		while(!Q.empty())
		{
			int a=Q.front().first,b=Q.front().second;
			Q.pop();
			if(G[a][b]/k>=F[a][b]) continue;
			for(int i=0;i<4;i++)
			{
				int x=a+dx[i],y=b+dy[i];
				if(min(x,y)>=1&&max(x,y)<=n&&s[x][y]!='T'&&G[x][y]==INF) G[x][y]=G[a][b]+1,Q.push({x,y});
			}
		}
		if(G[x2][y2]!=INF) l=mid+1,ans=mid;
		else r=mid-1;
	}
	cout<<ans;
}

• Subtask 1: 100 / 100