글 읽기 - 살려주세요.. 뭐가 틀렸을까요??

psi0613 5년 전 0

전체적으로 BFS 한 번 돌려서 녹는 날짜를 적어주고 이분탐색을 통해서 찾았는데 생각만큼 잘 안됐나 보네요.. 자꾸 틀리는거보니까

무엇이 잘못일까요..?

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1e9
#define xx first
#define yy second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
pii dir[] = { {1,0},{-1,0},{0,1},{0,-1} };
int N, M, graph[1505][1505], maxV;
vector<pii> vt;
bool visit[1505][1505];
struct info {
	int x, y, cnt;
};
queue<info> q;
queue<pii> qq;
void init() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			visit[i][j] = 0;
		}
	}
}
void go() {
	while (!q.empty()) {
		info p = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int px = p.x + dir[i].xx, py = p.y + dir[i].yy;
			if (px >= 1 && px <= N && py >= 1 && py <= M) {
				if (graph[px][py] == -1) {
					q.push({ px,py,p.cnt + 1 });
					graph[px][py] = p.cnt + 1;
					maxV = max(maxV, graph[px][py]);
				}
			}
		}
	}
}
bool can(int K) {
	qq.push({ vt[0].xx,vt[0].yy });
	visit[vt[0].xx][vt[0].yy] = 1;
	while (!qq.empty()) {
		pii p = qq.front(); qq.pop();
		for (int i = 0; i < 4; i++) {
			int px = p.xx + dir[i].xx, py = p.yy + dir[i].yy;
			if (px >= 1 && px <= N && py >= 1 && py <= M) {
				if (visit[px][py] == 0 && graph[px][py] <= K) {
					if (px == vt[1].xx && py == vt[1].yy) {
						return 1;
					}
					visit[px][py] = 1;
					qq.push({ px,py });
				}
			}
		}
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= M; j++) {
			if (s[j - 1] == '.') graph[i][j] = 0;
			else if (s[j - 1] == 'X') graph[i][j] = -1;
			else {
				vt.push_back({ i,j });
				graph[i][j] = 0;
			}
			if (graph[i][j] == 0) q.push({ i,j,0 });
		}
	}
	go();
	int s = 0, e = maxV, ans = 0;
	while (s <= e) {
		init();
		while (!qq.empty()) qq.pop();
		int mid = (s + e) / 2;
		if (can(mid)) {
			ans = max(ans, mid);
			e = mid - 1;
		}
		else {
			s = mid + 1;
		}
	}
	cout << ans;
}

psi0613 5년 전 0

찾았습니다~

이분탐색에서 max가아니라 min이였네요~~

저는 바보입니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

살려주세요.. 뭐가 틀렸을까요??

psi0613 5년 전 0

psi0613 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말