ROLLBAR Editorialist

#include <bits/stdc++.h>

using namespace std;

const int MX = (1009);

int T , n , m;
string valid[MX];
int sx , sy;
int bfs[MX][MX][3];

queue < pair < pair < int , int > , int > >  Q;


bool check(int x , int y){
    if(x < 1 || x > n || y < 1 || y > m) return 0;
    if(valid[x][y] == '0') return 0;
    return 1;
}

void add(int nx , int ny , int nstate , int ncost){
    if(bfs[nx][ny][nstate] != -1) return;
    bfs[nx][ny][nstate] = ncost;
    Q.push({{nx , ny},nstate});
}

void relax(int x , int y , int state){
    int C = bfs[x][y][state];

    if(state == 0){

        if(check(x , y - 1) && check(x , y - 2)) add(x , y - 2 , 1 , C + 1);
        if(check(x , y + 1) && check(x , y + 2)) add(x , y + 1 , 1 , C + 1);

        if(check(x - 1 , y) && check(x - 2 , y)) add(x - 2 , y , 2 , C + 1);
        if(check(x + 1 , y) && check(x + 2 , y)) add(x + 1 , y , 2 , C + 1);
    }

    if(state == 1){

        if(check(x - 1 , y) && check(x - 1 , y + 1)) add(x - 1 , y , 1 , C + 1);
        if(check(x + 1 , y) && check(x + 1 , y + 1)) add(x + 1 , y , 1 , C + 1);

        if(check(x , y + 2)) add(x , y + 2 , 0 , C + 1);
        if(check(x , y - 1)) add(x , y - 1 , 0 , C + 1);

    }

    if(state == 2){


        if(check(x , y - 1) && check(x + 1 , y - 1)) add(x , y - 1 , 2 , C + 1);
        if(check(x , y + 1) && check(x + 1 , y + 1)) add(x , y + 1 , 2 , C + 1);


        if(check(x + 2 , y)) add(x + 2 , y , 0 , C + 1);
        if(check(x - 1 , y)) add(x - 1 , y , 0 , C + 1);

    }


}
int main(){

  //  freopen("in.in","r",stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>T;

    while(T--){

        memset(bfs , -1 , sizeof(bfs));

        cin>>n>>m>>sx>>sy;

        for(int j = 1 ; j <= n ; j++){ cin>>valid[j]; valid[j] = "#" + valid[j]; };


        bfs[sx][sy][0] = 0;
        Q.push({{sx , sy} , 0});

        while(!Q.empty()){

            int x = Q.front().first.first , y = Q.front().first.second , state = Q.front().second; Q.pop();

            relax(x , y , state);

        }

        for(int j = 1 ; j <= n ; j++){
            for(int i = 1 ; i <= m ; i++){
                cout<<bfs[j][i][0]<<' ';
            }
            cout<<endl;
        }


    }




}