Submission #72906437

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a)  (a).begin(),(a).end()

using P=pair<ll,ll>;
using T=tuple<ll,ll,ll>;

#include <atcoder/all> 
using namespace atcoder;
// using mint=modint998244353;
// using mint=modint1000000007;
// int op(int a,int b){return (a+b);}
// int e(){return 0;}

int main() {
  int test;cin>>test;
  while(test--){
    int n,c;cin>>n>>c;
    c--;
    vector<string> s(n);
    rep(i,n)cin>>s[i];
    vector<int> mw(n,-1);
    rep(i,n){
      rep(j,n){
        if(s[i][j]=='#')mw[j]=i;
      }
    }

    vector<vector<int>> v(n,vector<int>(n,-1));
    queue<P> q;
    

    v[n-1][c]=2;
    q.push({n-2,c});
    if(c-1>=0)q.push({n-2,c-1});
    if(c+1<n)q.push({n-2,c+1});
    while(!q.empty()){
      int i=q.front().first;
      int j=q.front().second;
      q.pop();
      if(v[i][j]!=-1)continue;
      if(s[i][j]=='.'){
        if(i>mw[j])v[i][j]=2;
        else if(v[i+1][j]==2)v[i][j]=2;
        else v[i][j]=1;
      }
      if(s[i][j]=='#'){
        if(i==mw[j])v[i][j]=2;
        else if(v[i+1][j]==2)v[i][j]=2;
        else v[i][j]=0;
      }
      if(v[i][j]!=0 and i>0){
        q.push({i-1,j});
        if(j-1>=0)q.push({i-1,j-1});
        if(j+1<n)q.push({i-1,j+1});
      }
    }
    rep(j,n){
      if(v[0][j]==1 or v[0][j]==2)cout<<1;
      else cout<<0;
    }
    cout<<endl;
  }
}

Submission Info

Judge Result