Untitled

 avatar
unknown
plain_text
a year ago
4.6 kB
4
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, std::vector<bool> &visited_base) {
  if (visited[vertex]) {
    return false;
  }

  visited[vertex] = true;

  for (size_t i = 0; i < graph[vertex].neighbors.size(); ++i) {
    int to = graph[vertex].neighbors[i];

    if (match[to] == -1 || kuhn(match[to], graph, match, visited, visited_base)) {
      match[to] = vertex;
      visited_base[to] = true;
      return true;
    }
  }

  return false;
}

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;
      return true;
    }
  }

  return false;
}

inline std::vector<int> calc_match(const std::vector<vertex_type> &graph, std::vector<bool>& visited_base) {
  std::vector<int> match(graph.size(), -1);

  for (size_t i = 0; i < graph.size(); ++i) {
    for (size_t j = 0; j < graph[i].neighbors.size(); ++j) {
      int to = graph[i].neighbors[j];

      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, visited_base);
  }

  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;
}

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]);
        }
      }
    }
  }


  std::vector<bool> visited_base(graph.size(), false);
  auto match = calc_match(graph, visited_base);
  int max_match = count_match(match);

  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;

      if (match[data[r][c]] != -1) {
        auto copy_match = match;
        auto copy_visited = visited_base;
        copy_match[data[r][c]] = -1;
        copy_visited[data[r][c]] = false;

        for (size_t k = 0; k < match.size(); ++k) {
            if (copy_match[k] == data[r][c]) {
                copy_match[k] = -1;
                copy_visited[k] = false;
                break;
            }
        }

        // auto rev = visited_base[data[r][c]];
        // visited_base[data[r][c]] = false;

        for (size_t i = 0; i < graph.size(); ++i) {
            if (copy_visited[i]) {
                continue;
            }

            std::vector<bool> visited(graph.size(), false);
            kuhn(i, graph, copy_match, visited);
        }

        //visited_base[data[r][c]] = rev;
        auto match_count = count_match(copy_match);
        std::cout << (match_count == max_match ? 'L' : 'W');
      } else {
        std::cout << "L";
      }

      graph[data[r][c]].deleted = false;
    }

    std::cout << "\n";
  }

  return 0;
}
Editor is loading...
Leave a Comment