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

  return false;
}

bool kuhn_check(int vertex, const std::vector<vertex_type> &graph,
          const std::vector<int> &match, std::vector<bool> &visited) {
  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 (graph[to].deleted) {
      continue;
    }

    if (match[to] == -1 || kuhn_check(match[to], graph, match, visited)) {
      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);

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



    //auto match_count = max_match;

    if (match[data[r][c]] != -1) {
              graph[data[r][c]].deleted = true;

    
        auto copy_match = match;
        int to = match[data[r][c]];
        copy_match[data[r][c]] = -1;
        copy_match[to] = -1;

        std::vector<bool> visited(graph.size(), false);
        visited[data[r][c]] = true;

        for (size_t i = 0; i < graph.size(); ++i) {
            if (i == data[r][c] || copy_match[i] != -1) {
                continue;
            }

            kuhn(i, graph, copy_match, visited);
        }
        
        std::cout << (count_match(copy_match) == max_match ? 'L' : 'W');

        // match[data[r][c]] = to;
        // match[to] = data[r][c];

        // 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;
    } else {
        std::cout << 'L';
    }

     

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

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

  return 0;
}