Untitled
unknown
plain_text
a year ago
5.0 kB
5
Indexable
#include <cstdint> #include <ios> #include <iostream> #include <string> #include <vector> struct vertex_type { std::vector<int> neighbors; bool deleted{false}; vertex_type() { neighbors.reserve(4); } }; bool kuhn(int vertex, const std::vector<vertex_type> &graph, std::vector<int> &match, std::vector<bool> &visited) { if (visited[vertex] || graph[vertex].deleted) { return false; } visited[vertex] = true; for (size_t i = 0; i < graph[vertex].neighbors.size(); ++i) { int to = graph[vertex].neighbors[i]; if (graph[to].deleted) { continue; } if (match[to] == -1 || kuhn(match[to], graph, match, visited)) { match[to] = vertex; match[vertex] = to; //visited[to] = true; return true; } // auto b1 = match[to]; // auto b2 = match[vertex]; // match[to] = -1; // match[vertex] = -1; // if (!kuhn(b1, graph, match, visited)) { // match[to] = b1; // match[vertex] = b2; // } else { // match[to] = vertex; // match[vertex] = to; // return true; // } } return false; } inline std::vector<int> calc_match(const std::vector<vertex_type> &graph) { std::vector<int> match(graph.size(), -1); std::vector<bool> visited_base(graph.size(), false); for (size_t i = 0; i < graph.size(); ++i) { if (graph[i].deleted) { visited_base[i] = true; continue; } for (size_t j = 0; j < graph[i].neighbors.size(); ++j) { int to = graph[i].neighbors[j]; if (graph[to].deleted) { continue; } if (match[to] == -1) { match[to] = i; visited_base[i] = true; break; } } } for (size_t i = 0; i < graph.size(); ++i) { if (visited_base[i]) { continue; } std::vector<bool> visited(graph.size(), false); kuhn(i, graph, match, visited); } return match; } inline int count_match(const std::vector<int>& match) { int max_match = 0; for (size_t i = 0; i < match.size(); ++i) { if (match[i] != -1) { ++max_match; } } return max_match; } void print_match(const std::vector<int>& match) { for (int i = 0; i < match.size(); ++i) { std::cout << match[i] << " "; } std::cout << "\n"; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int row, col; std::cin >> row; std::cin >> col; std::vector<vertex_type> graph; graph.reserve(row * col); std::vector<std::vector<int>> data(row, std::vector<int>(col, -1)); char ch; int vertex_count = 0; for (int r = 0; r < row; ++r) { for (int c = 0; c < col; ++c) { std::cin >> ch; if (ch == '.') { data[r][c] = vertex_count; ++vertex_count; } } } for (int r = 0; r < row; ++r) { for (int c = 0; c < col; ++c) { if (data[r][c] != -1) { graph.emplace_back(); auto &vertex = graph[data[r][c]]; if (r > 0 && data[r - 1][c] != -1) { vertex.neighbors.push_back(data[r - 1][c]); } if (r + 1 < row && data[r + 1][c] != -1) { vertex.neighbors.push_back(data[r + 1][c]); } if (c > 0 && data[r][c - 1] != -1) { vertex.neighbors.push_back(data[r][c - 1]); } if (c + 1 < col && data[r][c + 1] != -1) { vertex.neighbors.push_back(data[r][c + 1]); } } } } auto match = calc_match(graph); //int max_match = count_match(match); // print_match(match); // std::cout << "\n"; for (int r = 0; r < row; ++r) { for (int c = 0; c < col; ++c) { if (data[r][c] == -1) { std::cout << "#"; continue; } graph[data[r][c]].deleted = true; bool same = true; //auto match_count = max_match; if (match[data[r][c]] != -1) { auto copy_match = match; int to = copy_match[data[r][c]]; copy_match[data[r][c]] = -1; copy_match[to] = -1; same = false; //std::vector<bool> visited(graph.size(), false); //kuhn(to, graph, copy_match, visited); //print_match(copy_match); { std::vector<bool> visited(graph.size(), false); if (kuhn(to, graph, copy_match, visited)) { same = true; } else { for (int i = 0; !same && i < match.size(); ++i) { if (copy_match[i] != -1) { continue; } { std::vector<bool> visited(graph.size(), false); if (kuhn(i, graph, copy_match, visited)) { same = true; break; } } } } } } graph[data[r][c]].deleted = false; std::cout << (same ? 'L' : 'W'); //std::cout << (match_count == max_match ? 'L' : 'W'); } std::cout << "\n"; } return 0; }
Editor is loading...
Leave a Comment