Submission #611686

#	Time	Username	Problem	Language	Result	Execution time	Memory
611686		Belgutei	Mecho (IOI09_mecho)	C++17	22 / 100	152 ms	8808 KiB

mecho

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int n,m;
int b[805][806];
queue<pair<int,int> > q;
int stx, sty;
int cnt[805][805];
int tmp[805][805];
bool check = 0;
char ch[805][805];

int main() {
	IOS
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= n; j ++) {
			cin >> ch[i][j];
			if(ch[i][j] == 'H') {
				b[i][j] = 1;
				q.push({i,j});
			}
			if(ch[i][j] == 'M') {
				stx = i;
				sty = j;
			}
		}
	}
	while(q.size() > 0) {
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		if(x > 1 && b[x - 1][y] == 0 && ch[x - 1][y] != 'T' && ch[x - 1][y] != 'D') {
			q.push({x - 1, y});
			b[x - 1][y] = b[x][y] + 1;
		}
		if(x < n && b[x + 1][y] == 0 && ch[x + 1][y] != 'T' && ch[x + 1][y] != 'D') {
			q.push({x + 1, y});
			b[x + 1][y] = b[x][y] + 1;
		}
		if(y > 1 && b[x][y - 1] == 0 && ch[x][y - 1] != 'T' && ch[x][y - 1] != 'D') {
			q.push({x, y - 1});
			b[x][y - 1] = b[x][y] + 1;
		}
		if(y < n && b[x][y + 1] == 0 && ch[x][y + 1] != 'T' && ch[x][y + 1] != 'D') {
			q.push({x, y + 1});
			b[x][y + 1] = b[x][y] + 1;
		}		
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= n; j ++) {
			if(b[i][j] == 0) b[i][j] = 1e9;
		}
	} 
	int l = 0;
	int r = n * n;
	while(l < r) {
		int mid = (l + r + 1) / 2;
		memset(cnt, -1, sizeof(cnt));
		while(q.size() > 0) q.pop();
		q.push({stx,sty});
		cnt[stx][sty] = mid;
		tmp[stx][sty] = m;
		bool ok = 0;
		while(q.size() > 0) {
			int x = q.front().ff;
			int y = q.front().ss;
			q.pop();
			int num = cnt[x][y];
			int move = tmp[x][y];
			if(tmp[x][y] == m) {
				num ++;
				move = 0;
			}
			move ++;
			//
			if(x > 1 && cnt[x - 1][y] == -1 && num < b[x - 1][y] && ch[x - 1][y] != 'T') {
				if(ch[x - 1][y] == 'D') { // home location
					ok = 1; break;
				}
				cnt[x - 1][y] = num;
				tmp[x - 1][y] = move;
				q.push({x - 1, y});
			}
			//
			if(x < n && cnt[x + 1][y] == -1 && num < b[x + 1][y] && ch[x + 1][y] != 'T') {
				if(ch[x + 1][y] == 'D') { // home location
					ok = 1; break;
				}
				cnt[x + 1][y] = num;
				tmp[x + 1][y] = move;
				q.push({x + 1, y});
			}
			//
			if(y > 1 && cnt[x][y - 1] == -1 && num < b[x][y - 1] && ch[x][y - 1] != 'T') {
				if(ch[x][y - 1] == 'D') { // home location
					ok = 1; break;
				}
				cnt[x][y - 1] = num;
				tmp[x][y - 1] = move;
				q.push({x, y - 1});
			}
			//
			if(y < n && cnt[x][y + 1] == -1 && num < b[x][y + 1] && ch[x][y + 1] != 'T') {
				if(ch[x][y + 1] == 'D') { // home location
					ok = 1; break;
				}
				cnt[x][y + 1] = num;
				tmp[x][y + 1] = move;
				q.push({x, y + 1});
			}
		}
		if(ok == 1) {
			check = 1;
			l = mid;
		}
		else r = mid - 1;
	}
	if(check == 1){
		cout << l - 1;
	} 
	else cout << -1;
}

• Subtask 1: 22 / 100