1613E - Crazy Robot - CodeForces Solution

#include <iostream>
#include<math.h>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <deque>
#include <random>
#include <algorithm>
#include <iterator>
#include <numeric>
#include <tuple>
#include <thread>
#include <chrono>
typedef long long ll;
using namespace std;
 
const ll mod = 1e9+7;
const ll inf = 1e18+1e17;
 

int bitcount(ll n) { return n == 0 ? 0 : bitcount(n & (n - 1)) + 1;}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}
ll binexp(ll a, ll b){
    if (!b) return 1;
    ll res = binexp(a, b/2);
    res = (res*res)%mod;
    if(b%2) res = (res*a)%mod;
    return res;
}
ll rev(ll x) {return binexp(x, mod - 2);}

vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,m;
        cin >> n >> m;
        vector<vector<char>> table(n+2, vector<char>(m+2, '#'));
        for(int i =1;i<=n;i++){
            for(int j=1;j<=m;j++) cin >> table[i][j];
        }
        vector<vector<int>> dp(n+2, vector<int>(m+2,0));
        vector<vector<bool>> used(n+2, vector<bool>(m+2,false));
        int start_x, start_y;
        for(int i =1;i<=n;i++){
            for(int j =1;j<=m;j++){
                if(table[i][j]=='.') dp[i][j] = 1;
                else if(table[i][j]=='L') {
                    start_y = i, start_x = j;
                    dp[i][j] = 2;
                }
            }
        }
        queue<pair<int,int>> q;
        q.push(make_pair(start_x, start_y));
        while(!q.empty()){
            auto p = q.front();
            q.pop();
            //dp[y][x] = A[i][j];
            int x = p.first, y = p.second;
            for(int i =0;i<4;i++){
                int new_x = x+dx[i], new_y = y + dy[i];
                if(dp[new_y][new_x]==1 && !used[new_y][new_x]){
                    int bad = 0, good = 0;
                    for(int i =0;i<4;i++){
                        if(dp[new_y+dy[i]][new_x+dx[i]] == 0) bad++;
                        if(dp[new_y+dy[i]][new_x+dx[i]]==2) good++;
                    }
                    if(bad>=2 || (bad==1 && good>=2) || (bad==0 && good>=3)){
                        used[new_y][new_x] = true;
                        dp[new_y][new_x] = 2;
                        table[new_y][new_x] = '+';
                        q.push(make_pair(new_x, new_y));
                    }
                }
            }
        }
        for(int i =1;i<=n;i++){
            for(int j=1;j<=m;j++) cout << table[i][j] << "";
            cout << '\n';
        }

    }
}