제출 #655587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
655587		Juan	Mecho (IOI09_mecho)	C++17	8 / 100	316 ms	4440 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
const int maxn = 805, INF = 0x3f3f3f3f;
#define pii pair<int, int>
#define ff first
#define ss second

int dist[maxn][maxn];
bool valid1[maxn][maxn];
pii ini, fim;
vector<pii> hives;
int px[4] = {1, -1, 0, 0}, py[4] = {0, 0, 1, -1};
int n, s;

bool solve(int T){
	bool valid[maxn][maxn];
	for(int i = 0; i < maxn; i++){
		for(int j = 0; j < maxn; j++) valid[i][j] = valid1[i][j];
	}
	memset(dist, 0, sizeof dist);
	queue<pii> qabel, qurso;

	for(pii x : hives)
		qabel.push(x);

	bool found = false, fuck = false;
	while(!qabel.empty()){
		int x, y;
		tie(x, y) = qabel.front();
		if(dist[x][y]==T) break;
		qabel.pop();

		for(int i = 0; i < 4; i++){
			int vx = x + px[i];
			int vy = y + py[i];
			if(make_pair(vx, vy) == fim) {fuck = true; break;}
			if(valid[vx][vy]) dist[vx][vy] = dist[x][y]+1, valid[vx][vy]=false, qabel.push({vx, vy}); 
		}
		if(fuck) break;
	}
	if(fuck) return false;

	if(valid[ini.ff][ini.ss]) qurso.push(ini);
	int cnt = 0;
	while(true){
		while(!qurso.empty()){// bfs urso
			int x, y;
			tie(x, y) = qurso.front();
			if(make_pair(x, y)==fim) {found = true; break;}
			int distu = dist[x][y];
			if(distu%s==0 && distu!=cnt*s) break;
			qurso.pop();

			for(int i = 0; i < 4; i++){
				int vx = x + px[i];
				int vy = y + py[i];
				if(valid[vx][vy]) dist[vx][vy] = dist[x][y]+1, valid[vx][vy] = false, qurso.push({vx, vy}); 
			}
		}
		cnt++;
		if(qurso.empty() || found) break;

		while(!qabel.empty()){// bfs abelhas
			int x, y;
			tie(x, y) = qabel.front();
			if(dist[x][y]==cnt+T) break;
			qabel.pop();

			for(int i = 0; i < 4; i++){
				int vx = x + px[i];
				int vy = y + py[i];
				if(make_pair(vx, vy) == fim) {fuck = true; break;}
				if(valid[vx][vy]) dist[vx][vy] = dist[x][y]+1, valid[vx][vy]=false, qabel.push({vx, vy}); 
			}
			if(fuck) break;
		}
		if(fuck) break;
	}

	if(fuck) {cout << "fuck\n"; return false;}
	else return found;
}

int main(){
	cin >> n >> s;

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			char c; cin >> c;
			if(c=='H') hives.push_back({i, j});
			if(c=='M') ini = {i, j};
			if(c=='D') fim = {i, j};
			if(c=='M' || c=='G' || c=='D') valid1[i][j] = true;
		}
	}

	int l=0, r = n*n, ans = INF;
	while(l<=r){
		int mid = (l+r)>>1;
		if(solve(mid)) l = mid+1, ans = mid;
		else r = mid-1;
	}

	cout << (ans==INF? -1 : ans) << '\n';
}

• Subtask 1: 8 / 100