제출 #59840

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59840		Tenuun	Mecho (IOI09_mecho)	C++11	8 / 100	560 ms	9208 KiB

mecho

#include<bits/stdc++.h>

using namespace std;

int n, s, u, V, x, y, z;
int a[802][802], dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0};
int bear[802][802];
int c[802][802];
vector<string> v;
vector<pair<int, int> >bee;
queue<pair<int, int>>q, b;

bool BFS(){
	queue<pair<pair<int, int>, int> >t;
	t.push({{x, y}, 0});
	bear[x][y]=0;
	while(!t.empty()){
		if(t.front().second>s) return false;
		x=t.front().first.first, y=t.front().first.second, z=t.front().second;
		t.pop();
		for(int i=0; i<4; i++){
			if(v[x+dx[i]][y+dy[i]]=='D') return true;
			if(v[x+dx[i]][y+dy[i]]=='G' && a[x+dx[i]][y+dy[i]]==-1 && bear[x+dx[i]][y+dy[i]]==-1){
				bear[x+dx[i]][y+dy[i]]=z+1;
				if(z+1>s) b.push({x+dx[i], y+dy[i]});
				else t.push({{x+dx[i], y+dy[i]}, z+1});
			}
		}
	}
	return false;
}

bool check(int m){
	for(int i=0; i<bee.size(); i++){
		x=bee[i].first, y=bee[i].second;
		a[x][y]=0;
		q.push(bee[i]);
	}
	b.push({u, V});
	c[u][V]=0;
	while(!q.empty()){
		x=q.front().first, y=q.front().second;
		z=a[x][y];
		if(z>=m){
			while(!b.empty() && c[b.front().first][b.front().second]<=z){
				x=b.front().first, y=b.front().second;
				b.pop();
				if(BFS()) return true;
			}
		}
		x=q.front().first, y=q.front().second;
		q.pop();
		for(int i=0; i<4; i++){
			if((v[x+dx[i]][y+dy[i]]=='G' || v[x+dx[i]][y+dy[i]]=='M') && a[x+dx[i]][y+dy[i]]==-1){
				a[x+dx[i]][y+dy[i]]=a[x][y]+1;
				q.push({x+dx[i], y+dy[i]});
			}
		}
	}
	return false;
}

void solve(){
	int l=1, r=2*n, m=(l+r+1)/2;
	while(l<r){
		memset(a, -1, sizeof a);
		memset(c, -1, sizeof c);
		memset(bear, -1, sizeof bear);
		while(!q.empty())q.pop();
		while(!b.empty())b.pop();
		if(check(m)) l=m;
		else r=m-1;
		m=(l+r+1)/2;
	}
	cout << l-1;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> s;
	string tmp, k;
	for(int i=0; i<n+2; i++) tmp+='T';
	v.push_back(tmp);
	for(int i=1; i<=n; i++){
		cin >> k;
		k='T'+k+'T';
		for(int j=1; j<=n; j++){
			if(k[j]=='M'){
				u=i, V=j;
			}
			if(k[j]=='H'){
				bee.push_back({i, j});
			}
		}
		v.push_back(k);
	}
	v.push_back(tmp);
	solve();
	return 0;
}

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

mecho.cpp: In function 'bool check(int)':
mecho.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<bee.size(); i++){
               ~^~~~~~~~~~~

• Subtask 1: 8 / 100