Submission #121464

#	Time	Username	Problem	Language	Result	Execution time	Memory
121464		TadijaSebez	Mecho (IOI09_mecho)	C++11	100 / 100	205 ms	6908 KiB

mecho

#include <stdio.h>
#include <queue>
using namespace std;
const int N=805;
char Base[N][N];
int Move[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
queue<int> q;
int dist[N][N];
void BFS(int s)
{
	while(q.size())
	{
		int x=q.front()/N;
		int y=q.front()%N;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=x+Move[i][0];
			int ny=y+Move[i][1];
			if(Base[nx][ny]=='G' && dist[nx][ny]==-1)
			{
				dist[nx][ny]=dist[x][y]+s;
				q.push(nx*N+ny);
			}
		}
	}
}
int tmp[N][N];
bool Check(int n, int s, int sx, int sy, int fx, int fy, int mid)
{
	int i,j;
	for(i=1;i<=n;i++) for(j=1;j<=n;j++) tmp[i][j]=-1;
	if(dist[sx][sy]<=mid*s) return false;
	tmp[sx][sy]=mid*s;
	q.push(sx*N+sy);
	while(q.size())
	{
		int x=q.front()/N;
		int y=q.front()%N;
		q.pop();
		for(i=0;i<4;i++)
		{
			int nx=x+Move[i][0];
			int ny=y+Move[i][1];
			if((Base[nx][ny]=='G' && tmp[nx][ny]==-1 && dist[nx][ny]>tmp[x][y]+1) || (Base[nx][ny]=='D' && tmp[nx][ny]==-1))
			{
				tmp[nx][ny]=tmp[x][y]+1;
				q.push(nx*N+ny);
			}
		}
	}
	return tmp[fx][fy]!=-1;
}
int main()
{
	int n,s,i,j,sx,sy,fx,fy;
	scanf("%i %i",&n,&s);
	for(i=1;i<=n;i++) for(j=1;j<=n;j++) dist[i][j]=-1;
	for(i=1;i<=n;i++)
	{
		scanf("%s",Base[i]+1);
		for(j=1;j<=n;j++)
		{
			if(Base[i][j]=='M') sx=i,sy=j,Base[i][j]='G';
			if(Base[i][j]=='D') fx=i,fy=j;
			if(Base[i][j]=='H') q.push(i*N+j),dist[i][j]=0;
		}
	}
	BFS(s);
	int top=n*n,bot=0,mid,ans=-1;
	while(top>=bot)
	{
		mid=top+bot>>1;
		if(Check(n,s,sx,sy,fx,fy,mid)) ans=mid,bot=mid+1;
		else top=mid-1;
	}
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:73:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
mecho.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&s);
  ~~~~~^~~~~~~~~~~~~~~
mecho.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",Base[i]+1);
   ~~~~~^~~~~~~~~~~~~~~~
mecho.cpp:74:11: warning: 'fy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(Check(n,s,sx,sy,fx,fy,mid)) ans=mid,bot=mid+1;
      ~~~~~^~~~~~~~~~~~~~~~~~~~~
mecho.cpp:74:11: warning: 'fx' may be used uninitialized in this function [-Wmaybe-uninitialized]
mecho.cpp:74:11: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
mecho.cpp:74:11: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 100 / 100