Untitled

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

    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;

        std::vector<bool> visited(graph.size(), false);
        kuhn(to, graph, copy_match, visited);
        //print_match(copy_match);

        // for (int i = 0; i < match.size(); ++i) {
        //     if (match[i] != -1 || i == data[r][c]) {
        //         continue;
        //     }
        //     std::vector<bool> visited(graph.size(), false);
        //     kuhn(i, graph, copy_match, visited);
        // }

        match_count = count_match(copy_match);
    }

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

      std::cout << (match_count == max_match ? 'L' : 'W');
    }

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

  return 0;
}