제출 #916016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916016		gaga999	Mecho (IOI09_mecho)	C++17	100 / 100	282 ms	2772 KiB

mecho

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define SIZE 805
#define all(x) x.begin(), x.end()
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;

int n, mxstep;
char a[SIZE][SIZE];
bool vis[SIZE][SIZE];
bool bee[SIZE][SIZE];
struct node
{
	int x, y;
	int s;
	bool operator ==(node b)
	{
		return x==b.x && y==b.y;
	}
};
vector<node> hive;
node start;
node endpo;

int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};

bool bfs(int wait)
{
	queue<node> q;	// bear
	q.push(start);
	queue<node> Q;	// bee
	memset(vis, 0, sizeof(vis));
	memset(bee, 0, sizeof(bee));
	vis[start.x][start.y]=1;
	for(node t:hive)
	{
		bee[t.x][t.y]=1;
		Q.push(t);
	}
	// 吃蜜时间蜜蜂围攻 
	while(!Q.empty() && Q.front().s<wait)
	{
		node w=Q.front(); Q.pop();
		int i=w.x, j=w.y;
		for(int k=0; k<4; k++)
		{
			int ni=i+dx[k];
			int nj=j+dy[k];
			// 不越界 
			if(ni<0 || ni>=n || nj<0 || nj>=n)
				continue;
			// 不走回头路 
			if(bee[ni][nj])
				continue;
			// 不入禁区 
			if(a[ni][nj]=='D' || a[ni][nj]=='T')
				continue;
			bee[ni][nj]=1;
			Q.push({ni, nj, w.s+1});
		}
	}
	// 原始位置已被攻占 
	if(bee[start.x][start.y])
		return 0;
	int steps=1;	// 行走的次数 
	while(!q.empty())
	{
		// 小熊先走 
		while(!q.empty() && q.front().s<steps*mxstep)
		{
			node w=q.front(); q.pop();
			int i=w.x, j=w.y;
			if(w==endpo) return 1;
			if(bee[i][j]) continue;
			for(int k=0; k<4; k++)
			{
				int ni=i+dx[k];
				int nj=j+dy[k];
				// 不越界
				if(ni<0 || ni>=n || nj<0 || nj>=n)
					continue;
				// 不被蜜蜂蛰 
				if(bee[ni][nj])
					continue;
				// 不走回头路 
				if(vis[ni][nj])
					continue;
				// 不入禁区 
				if(a[ni][nj]=='T')
					continue;
				vis[ni][nj]=1;
				q.push({ni, nj, w.s+1});
			}
		}
		// 蜜蜂后走
		while(!Q.empty() && Q.front().s<wait+steps)
		{
			node w=Q.front(); Q.pop();
			int i=w.x, j=w.y;
			for(int k=0; k<4; k++)
			{
				int ni=i+dx[k];
				int nj=j+dy[k];
				// 不越界
				if(ni<0 || ni>=n || nj<0 || nj>=n)
					continue;
				// 不走回头路 
				if(bee[ni][nj])
					continue;
				// 不入禁区 
				if(a[ni][nj]=='D' || a[ni][nj]=='T')
					continue;
				bee[ni][nj]=1;
				Q.push({ni, nj, w.s+1});
			}
		}
		steps++;
	}
	return 0;
}

signed main()
{
	cin>>n>>mxstep;
	int si, sj;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='H')
				hive.push_back({i, j, 0});
			if(a[i][j]=='M')
				start={i, j, 0};
			if(a[i][j]=='D')
				endpo={i, j, 0};
		}
	int l=0, r=n*n;
	int ans=-1;
	while(l<=r)
	{
		int m=(l+r)>>1;
		if(bfs(m))
		{
			ans=m;
			l=m+1;
		}
		else
			r=m-1;
	}
	cout<<ans;

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'int main()':
mecho.cpp:126:6: warning: unused variable 'si' [-Wunused-variable]
  126 |  int si, sj;
      |      ^~
mecho.cpp:126:10: warning: unused variable 'sj' [-Wunused-variable]
  126 |  int si, sj;
      |          ^~

• Subtask 1: 100 / 100