Submission #138725

#	Time	Username	Problem	Language	Result	Execution time	Memory
138725		Boxworld	Mecho (IOI09_mecho)	C++14	19 / 100	1089 ms	7004 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
const int N=810;
char G[N][N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int T[N][N],d[N][N];
int n,s,sx,sy,fx,fy;
bool vaild(int x,int y){
	if (G[x][y]=='T'||G[x][y]=='H')return 0;
	if (x<1||x>n||y<1||y>n)return 0;
	return 1;
}
bool bfs(int time){
	memset(d,-1,sizeof(d));
	d[sx][sy]=time*s-1;
	queue<int> Q;
	Q.push(sx*N+sy);
	while(!Q.empty()){
		int x=Q.front()/N,y=Q.front()%N;Q.pop();
		if (d[x][y]/s>=T[x][y])continue;
		for (int k=0;k<4;k++){
			int X=x+dx[k],Y=y+dy[k];
			if (d[X][Y]>=0)continue;
			if (!vaild(X,Y))continue;
			if (X==fx&&Y==fy)return 1;
			d[X][Y]=d[x][y]+1;
			Q.push(X*N+Y);
		}
	}
	return 0;
}
int main(){
	scanf("%d%d",&n,&s);
	for (int i=1;i<=n;i++)scanf("%s",G[i]+1);
	memset(T,-1,sizeof(T));
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++){
		if (G[i][j]=='M')sx=i,sy=j;
		if (G[i][j]=='D')fx=i,fy=j,T[i][j]=0x7fffffff;
		if (G[i][j]=='H')T[i][j]=0;
	}
	for (int t=1;;t++){
		int ok=0;
		for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		if (T[i][j]==t-1){
			for (int k=0;k<4;k++){
				int X=i+dx[k],Y=j+dy[k];
				if (vaild(X,Y)&&T[X][Y]<0){
					T[X][Y]=t;
					ok=1;
				}
			}
		}
		if (!ok)break;
	}
	for (int i=T[sx][sy];i>=0;i--)
	if (bfs(i)){
		printf("%d\n",i);
		return 0;
	}else{
	//	printf("Time:%d\n",i);
	//	for (int x=1;x<=n;x++){
//		for (int j=1;j<=n;j++)printf("%2d",d[x][j]);printf("\n");}
	}
	printf("-1\n");
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:33: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:34:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1;i<=n;i++)scanf("%s",G[i]+1);
                        ~~~~~^~~~~~~~~~~~~

• Subtask 1: 19 / 100