https://www.acmicpc.net/problem/2842
2842번: 집배원 한상덕
상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int dx[] = {-1,-1,-1,0,0,1,1,1};
int dy[] = { -1,0,1,-1,1,-1,0,1 };
int n;
char wichi[55][55];
int slope[55][55];
bool check[55][55];
vector<int> tire;
pair<int, int> start;
int cnt = 0;
int bfs(int low, int high)
{
queue<pair<int, int>> q;
if (slope[start.first][start.second] >= tire[low] && slope[start.first][start.second] <= tire[high])
{
q.push(make_pair(start.first, start.second));
check[start.first][start.second] = true;
}
int visit = 0;
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 8; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n)
{
if (check[nx][ny] == false && slope[nx][ny] >= tire[low] && slope[nx][ny] <= tire[high])
{
check[nx][ny] = true;
q.push(make_pair(nx, ny));
if (wichi[nx][ny] == 'K')
visit++;
}
}
}
}
if (visit == cnt)
return 1;
else
return 2;
}
// 이분탐색
void solve()
{
sort(tire.begin(), tire.end());
tire.erase(unique(tire.begin(), tire.end()), tire.end());
//low와 high는 index이다
int low = 0;
int high = 0;
int result = 987654321;
while (low < tire.size())
{
memset(check, false, sizeof(check));
int ans = bfs(low, high);
if (ans == 1)
{
result = min(result, tire[high] - tire[low]);
low++;
}
else
{
if (high < tire.size() - 1)
high++;
else break;
}
}
cout << result << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> wichi[i][j];
if (wichi[i][j] == 'P')
{
start.first = i;
start.second = j;
}
else if (wichi[i][j] == 'K')
cnt++;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> slope[i][j];
tire.push_back(slope[i][j]);
}
}
solve();
return 0;
}
|
cs |
'이분 탐색' 카테고리의 다른 글
| 그래도 수명이 절반이 되어서는.. (1) | 2024.01.28 |
|---|---|
| 영어 공부 (0) | 2024.01.24 |
| 사탕 가방 (1) | 2024.01.23 |
| 예산 (upsolve 필요) (0) | 2023.04.29 |
| 숫자 카드 (0) | 2023.04.08 |