Submission #138704

#	Time	Username	Problem	Language	Result	Execution time	Memory
138704		Boxworld	Mecho (IOI09_mecho)	C++14	14 / 100	1088 ms	9720 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MX=1000,inf=0x7fffffff;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
char G[MX][MX];
int d[MX][MX],d1[MX][MX];
int n,s,sx,sy,fx,fy,ans=-1;
queue<int> Q1[2];
int bfs(int time){
	memset(d1,0,sizeof(d1));
	d1[sx][sy]=-1;
	queue<int> Q;
	Q.push(sx*MX+sy);
	while(!Q.empty()){
		int x=Q.front()/MX,y=Q.front()%MX;Q.pop();
	//	printf("x=%d,y=%d time=%d\n",x,y,d1[x][y]/s+time);
		if (time>0&&d1[x][y]/s+time>=d[x][y])continue;
		for (int i=0;i<4;i++){
			int X=x+dx[i],Y=y+dy[i];
			if (X<1||X>n||Y<1||Y>n)continue;
			if (X==fx&&Y==fy)return 1;
			if (G[X][Y]=='T'||G[X][Y]=='H'||d1[X][Y]>0)continue;
			d1[X][Y]=d1[x][y]+1;
			Q.push(X*MX+Y);
	//		printf("INQ T:%d X:%d Y:%d\n",d1[X][Y],X,Y);
		}
	//	printf("#\n");
	//	for (int i=1;i<=n;i++){
	//		for (int j=1;j<=n;j++)printf("%2d",d1[i][j]);printf("\n");
	//	}
	}
	return 0;
}
int main(){
	scanf("%d%d",&n,&s);
	memset(d,-1,sizeof(d));
	for (int i=1;i<=n;i++){
		scanf("%s",G[i]+1);
		for (int j=1;j<=n;j++){
			if (G[i][j]=='H')d[i][j]=0,Q1[0].push(i*MX+j);
			if (G[i][j]=='M')sx=i,sy=j;
			if (G[i][j]=='D')d[i][j]=inf,fx=i,fy=j;
		}
	}
	
	int cnt=0;
	for (int t=1;;t++){
		if (Q1[cnt].empty())break;
		while(!Q1[cnt].empty()){
			int xy=Q1[cnt].front();Q1[cnt].pop();
			int x=xy/MX,y=xy%MX;
			for (int i=0;i<4;i++){
				int X=x+dx[i],Y=y+dy[i];
				if (d[X][Y]>=0||G[X][Y]=='D'||G[X][Y]=='T')continue;
				d[X][Y]=t;
				Q1[1-cnt].push(X*MX+Y);
			}
		}
		cnt=1-cnt;
	}
	
	for (int t=d[sx][sy];t>=0;t--)
	if (bfs(t)){
		printf("%d\n",t);
		return 0;
	}
	printf("-1");
/*	if (bfs(-1)){
		ans=0;
		int l=0,m,r=d[sx][sy];
		while(l<r){
			m=(l+r)/2;
			if (bfs(m)){
				l=m+1;
				ans=m;
			}else{
				r=m-1;
			}
		}
	}
	printf("%d\n",ans);*/
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&s);
  ~~~~~^~~~~~~~~~~~~~
mecho.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",G[i]+1);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 14 / 100