Search

집배원 한상덕

Created
2021/03/23 01:58
문제 번호
2842
카테고리
그래프
이분탐색
DFS
BFS
투포인터

Memo

Code

제출 날짜

@12/9/2020

메모리

2152 KB

시간

276 ms
#include <iostream> #include <vector> #include <string> #include <algorithm> int g_row_size; int g_matrix_size; int g_search_count; int g_result; std::string g_map; std::vector<int> g_alt; std::vector<int> g_unique_alt; std::pair<int, int> g_post_office; std::pair<int, std::vector<std::pair<int, int> > > g_houses; std::vector<std::pair<int, int> > g_displacement; std::vector<bool> g_visited; void pre_setting(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); } void input_action(void) { int index; std::cin >> g_row_size; g_matrix_size = g_row_size * g_row_size; g_map.resize(g_matrix_size); g_alt.resize(g_matrix_size); g_unique_alt.resize(g_matrix_size); g_displacement = { {0, 1}, {0, -1}, {1, 0}, {-1 ,0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1} }; g_result = 1e6; g_houses.first = 0; index = -1; while (++index < g_matrix_size) { std::cin >> g_map[index]; if (g_map[index] == 'P') g_post_office = std::make_pair(index / g_row_size, index % g_row_size); else if (g_map[index] == 'K') { ++g_houses.first; g_houses.second.push_back(std::make_pair(index / g_row_size, index % g_row_size)); } } index = -1; while (++index < g_matrix_size) { std::cin >> g_alt[index]; g_unique_alt[index] = g_alt[index]; } std::sort(g_unique_alt.begin(), g_unique_alt.end()); g_unique_alt.erase(std::unique(g_unique_alt.begin(), g_unique_alt.end()), g_unique_alt.end()); } void depth_search(int x, int y, int min_alt, int max_alt) { int index; index = -1; if (x < 0 || y < 0 || x >= g_row_size || y >= g_row_size || g_visited[x * g_row_size + y] || min_alt > g_alt[x * g_row_size + y] || max_alt < g_alt[x * g_row_size + y]) return ; g_visited[x * g_row_size + y] = true; if (g_map[x * g_row_size + y] == 'K') ++g_search_count; while (++index < 8) depth_search(g_displacement[index].first + x, g_displacement[index].second + y, min_alt, max_alt); } void two_pointer_search(void) { int search_size; int s_index; int e_index; search_size = static_cast<int>(g_unique_alt.size()); s_index = 0; e_index = 0; while (e_index < search_size) { while (s_index < search_size) { g_search_count = 0; g_visited = std::vector<bool>(g_matrix_size, false); depth_search(g_post_office.first, g_post_office.second, g_unique_alt[s_index], g_unique_alt[e_index]); if (g_houses.first != g_search_count) break ; if (g_result > g_unique_alt[e_index] - g_unique_alt[s_index]) g_result = g_unique_alt[e_index] - g_unique_alt[s_index]; ++s_index; } ++e_index; } } void output_action(void) { std::cout << g_result; } void solution(void) { input_action(); two_pointer_search(); output_action(); } int main(void) { pre_setting(); solution(); return (0); }
C++