Submission #72905881

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long

int dx[3] = {-1, -1, -1};
int dy[3] = {-1, 0, 1};
void solve(){

    int N, C; cin >> N >> C;
    // N --;
    // C --;
    vector<string> str(N);
    for(int i = 0;i < N;i ++ ){
        cin >> str[i];
    }

    vector<vector<int>> s(N,vector<int>(N, 0));
    vector<vector<int>> st(N, vector<int>(N, false));
    for(int col = 0;col < N;col ++ ){
        for(int row = 0;row < N;row ++ ){
            if(row == 0) s[col][row] = (str[row][col] == '#');
            else s[col][row] = s[col][row - 1] + (str[row][col] == '#');
        }
    }

    vector<int> col(N, 0);

    auto bfs = [&](int xx,int yy)->void{
        queue<array<int,2>> qu;
        qu.push({xx, yy});


        while(!qu.empty()){

            auto [x, y] = qu.front();
            st[x][y] = true;
            qu.pop();

            if(x == 0){
                col[y] = true;
            }

            for(int i = 0;i < 3;i ++ ){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || nx >= N || ny < 0 || ny >= N)
                    continue;
                
                if(!st[nx][ny] && str[nx][ny] != '#'){
                    st[nx][ny] = 1;
                    qu.push({nx, ny});
                }

                if(s[ny][N - 1] - s[ny][nx] == 0){
                    // cout << "nx " << nx << " ";
                    // cout << "ny " << " " << ny << "\n";
                    if(!st[nx][ny]){
                        st[nx][ny] = 1;
                        qu.push({nx, ny});
                    }
                    col[ny] = 1;
                }

            }    
        }

    };

    bfs(N - 1, C - 1);

    for(int i = 0;i < N;i ++ ){
        cout  << col[i];
    }

    cout << "\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1; 

    cin >> T;

    while(T -- ){
        solve();
    }


    return 0;
}

Submission Info

Judge Result