제출 #611947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
611947		Belgutei	Mecho (IOI09_mecho)	C++17	79 / 100	173 ms	10092 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];
bool visited[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;
			else b[i][j] --;
		}
	} 

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

• Subtask 1: 79 / 100