Submission #138843

#	Time	Username	Problem	Language	Result	Execution time	Memory
138843		StevenH	Mecho (IOI09_mecho)	C++14	9 / 100	1085 ms	65540 KiB

mecho

#include <iostream>
#include <fstream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int _map[805][805];
int map[805][805];
int n,s;
struct Node{
	int x,y,tm;
};
void print()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			printf("%c",map[i][j]);
		printf("\n");
	}
}
void run(int t)
{
	for(int i=0;i<t;i++)
	{
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
				if(map[j][k]=='H')
				{
					if(j+1< n && map[j+1][k]=='G')map[j+1][k]='K';
					if(j-1>=0 && map[j-1][k]=='G')map[j-1][k]='K';
					if(k+1< n && map[j][k+1]=='G')map[j][k+1]='K';
					if(k-1>=0 && map[j][k-1]=='G')map[j][k-1]='K';
				}
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
				if(map[j][k]=='K')
					map[j][k]='H';
	}

}
void copy()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			map[i][j]=_map[i][j];
}
bool f[805][805];
bool vis[805][805];
int ss[2000000][2];
int k;
bool judge(int x,int y)
{
	if(x<0 || y<0 || x>=n || y>=n)return 0;
	if(vis[x][y])return 0;
	if(map[x][y]=='T')return 0;
	if(map[x][y]=='H')return 0;
	return 1;

}
int flag;
void dfs(int x,int y,int p)
{
	//printf("%d %d\n",x,y);
	f[x][y]=1;
	if(flag)return;
	if(map[x][y]=='D')
	{
		//printf("%d\n",p);
		k=1;
		ss[0][0]=x;
		ss[0][1]=y;
		flag=1;
		return;
	}
	if(p==s)
	{
		ss[k][0]=x;
		ss[k][1]=y;
		k++;
		f[x][y]=0;
		return;
	}
	if(judge(x+1,y))dfs(x+1,y,p+1);
	if(judge(x-1,y))dfs(x-1,y,p+1);
	if(judge(x,y+1))dfs(x,y+1,p+1);
	if(judge(x,y-1))dfs(x,y-1,p+1);

}
bool bfs(int sx,int sy,int t)
{
	memset(vis,0,sizeof(vis));
	copy();
	run(t);
	queue<Node> que;
	que.push({sx,sy,0});
	vis[sx][sy]=1;
	int tm=0;
	while(!que.empty())
	{
		Node now=que.front();
		if(now.tm>tm)
			run(1),tm++;
		que.pop();
		k=0;
		memset(f,0,sizeof(f));
		flag=0;
		dfs(now.x,now.y,0);
		//if(k>0)printf("%d %d %d\n",now.x,now.y,k);
		for(int i=0;i<k;i++)
		{
			int x=ss[i][0];
			int y=ss[i][1];
			vis[x][y]=1;
			if(map[x][y]=='D')return 1;
			else que.push({x,y,now.tm+1});
		}
		//if(k>0)printf("\n");
	}
	return 0;

}
int main()
{
	//freopen("sample.in","rb",stdin);
	int sx,sy;
	scanf("%d%d",&n,&s);
	//printf("%d %d",n,s);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			char res;
			while(scanf("%c",&_map[i][j]))
				if(_map[i][j]>='A' && _map[i][j]<='Z')
					break;
			if(_map[i][j]=='M')
				sx=i,sy=j;
		}
	if(!bfs(sx,sy,0))printf("-1");
	else
	{
		if(!(sx,sy,1))printf("0");
		else 
		{
			int left=1,right=1;
			while(bfs(sx,sy,right))left=right,right*=2;
			if(right==1)printf("1");
			else
			{
				right--;
				//printf("%d*%d\n",left,right);
				while(left<right)
				{
					int mid=(left+right)/2;
					if((left+right)%2==1)mid++;
					if(bfs(sx,sy,mid))left=mid;
					else right=mid-1;
				}
				printf("%d",left);
			}
		}
	}

	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:133:32: warning: format '%c' expects argument of type 'char*', but argument 2 has type 'int*' [-Wformat=]
    while(scanf("%c",&_map[i][j]))
                     ~~~~~~~~~~~^
mecho.cpp:132:9: warning: unused variable 'res' [-Wunused-variable]
    char res;
         ^~~
mecho.cpp:142:11: warning: left operand of comma operator has no effect [-Wunused-value]
   if(!(sx,sy,1))printf("0");
           ^~
mecho.cpp:142:14: warning: right operand of comma operator has no effect [-Wunused-value]
   if(!(sx,sy,1))printf("0");
              ^
mecho.cpp:127: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:146:13: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
    while(bfs(sx,sy,right))left=right,right*=2;
          ~~~^~~~~~~~~~~~~
mecho.cpp:146:13: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 9 / 100