제출 #521191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521191		zhangjishen	Mecho (IOI09_mecho)	C++98	100 / 100	188 ms	6268 KiB

mecho

#include<bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = 810, inf = 1e9;
const int mv[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int n, s, mx, my, dx, dy, d1[MAXN][MAXN], d2[MAXN][MAXN];
char g[MAXN][MAXN];

// bfs
bool valid(int x, int y){
	return x >= 1 && x <= n && y >= 1 && y <= n;
}

void bfs1(){
	queue<pii> q;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(g[i][j] == 'H')
				d1[i][j] = 0, q.push(mp(i, j));
			else d1[i][j] = inf;
	while(!q.empty()){
		pii u = q.front(); q.pop();
		for(int k = 0; k < 4; k++){
			int x = u.fi + mv[k][0];
			int y = u.se + mv[k][1];
			if(valid(x, y) && g[x][y] != 'T' && g[x][y] != 'D' && d1[x][y] == inf){
				d1[x][y] = d1[u.fi][u.se] + 1;
				q.push(mp(x, y));
			}
		}
	}
}

bool check(int t){
	queue<pii> q;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			d2[i][j] = inf;
	if(t < d1[mx][my])
		d2[mx][my] = 0, q.push(mp(mx, my));
	while(!q.empty()){
		pii u = q.front(); q.pop();
		for(int k = 0; k < 4; k++){
			int x = u.fi + mv[k][0];
			int y = u.se + mv[k][1];
			if(valid(x, y) && g[x][y] != 'T' && d2[x][y] == inf && (t + (d2[u.fi][u.se] + 1) / s < d1[x][y])){
				d2[x][y] = d2[u.fi][u.se] + 1;
				q.push(mp(x, y));
			}
		}
	}
	return d2[dx][dy] != inf;
}

int main(){
	// input
	scanf("%d %d", &n, &s);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++){
			scanf(" %c", &g[i][j]);
			if(g[i][j] == 'M')
				mx = i, my = j;
			if(g[i][j] == 'D')
				dx = i, dy = j;
		}
	// prework(bfs)
	bfs1();
	// binary search
	int l = -1, r = n * n, mid;
	while(l < r){
		mid = (l + r + 1) / 2;
		if(check(mid))
			l = mid;
		else r = mid - 1;
	}
	printf("%d\n", l);
}

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

mecho.cpp: In function 'int main()':
mecho.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d %d", &n, &s);
      |  ~~~~~^~~~~~~~~~~~~~~~~
mecho.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |    scanf(" %c", &g[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100