제출 #611819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
611819		Belgutei	Mecho (IOI09_mecho)	C++17	20 / 100	1093 ms	13940 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;
			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));
		while(q.size() > 0) q.pop();
		//
		q.push({stx, sty});
		if(mid >= b[stx][sty]) {
			r = mid - 1;
			continue;
		}
		cnt[stx][sty] = mid;
		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;
			}
			for(int i = 1; i <= m; i ++) {
				for(int j = 0; j <= i; j ++) {
					int xx = x - j;
					int yy = y - (i - j);
					if(cnt[xx][yy] == -1 && cnt[x][y] + 1 < b[xx][yy] && ch[xx][yy] != 'T') {
						q.push({xx,yy});
						cnt[xx][yy] = cnt[x][y] + 1;
					} 
				}
				for(int j = 0; j <= i; j ++) {
					int xx = x - (i - j);
					int yy = y + j;
					if(cnt[xx][yy] == -1 && cnt[x][y] + 1 < b[xx][yy] && ch[xx][yy] != 'T') {
						q.push({xx,yy});
						cnt[xx][yy] = cnt[x][y] + 1;
					} 
				}
				for(int j = 0; j <= i; j ++) {
					int xx = x + j;
					int yy = y + (i - j);
					if(cnt[xx][yy] == -1 && cnt[x][y] + 1 < b[xx][yy] && ch[xx][yy] != 'T') {
						q.push({xx,yy});
						cnt[xx][yy] = cnt[x][y] + 1;
					} 
				}
				for(int j = 0; j <= i; j ++) {
					int xx = x + (i - j);
					int yy = x - j;
					if(cnt[xx][yy] == -1 && cnt[x][y] + 1 < b[xx][yy] && ch[xx][yy] != 'T') {
						q.push({xx,yy});
						cnt[xx][yy] = cnt[x][y] + 1;
					} 
				}
			}
		}	
		if(ok == 1) {
			check = 1;
			l = mid;
		}
		else r = mid - 1;

	}
	if(check == 1){
		cout << l;
	} 
	else cout << -1;
}

• Subtask 1: 20 / 100