この問題を解くために、動的計画法 (DP) を利用します。
\(dp[i][j] = \{\) 高橋君が \((i,j)\) に侵入できるなら \(1\) 、侵入できないなら \(0\) \(\}\) という DP を実行することを考えます。

最初は、全ての \(i,j\) について \(dp[i][j]=0\) と初期化します。
その後、全ての \(i\) について \((i,C)\) には侵入可能なので \(dp[i][C]=1\) とします。
そして、以下のように DP テーブルを更新します。

• \(i=N-1,N-2,\dots,1\) について以下を実行する。
  • \(j=1,2,\dots,N\) について、 \(dp[i][j]\) を更新する。
    • \(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]\) のいずれかが \(1\) であれば、壁マスの条件を無視すれば \((i,j)\) に侵入することができる。以降はこのケースのみを考慮する。
    • もし既に \(dp[i][j]=1\) であれば、既に \((i,j)\) に到達可能であることが分かっているためこれ以上の調査は不要である。
    • もし \((i,j)\) が空きマスであれば、侵入可能なので \(dp[i][j]=1\) とする。
    • もし \((i,j)\) が壁マスである時、全ての \(i < k \le N\) について \((k,j)\) が空きマスであれば、 \((i,j)\) およびそれより上の \(j\) 列目のマスについて壁を壊して侵入できることが分かるので、全ての \(1 \le k \le i\) について \(dp[k][j]=1\) とする。この判定は、 \(j\) 列目のうち最も下の壁マスはどこかを予め調べておくことで高速に行うことができる。

この解法の時間計算量は \(O(N^2)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int t;
  cin >> t;
  while(t--){
    int n,c;
    cin >> n >> c;
    c--;
    vector<string> s(n);
    vector<int> low(n,-1);
    for(int i=0;i<n;i++){
      cin >> s[i];
      for(int j=0;j<n;j++){
        if(s[i][j]=='#'){ low[j]=i; }
      }
    }
    vector<vector<int>> dp(n,vector<int>(n,0));
    for(int i=0;i<n;i++){dp[i][c]=1;}
    for(int i=n-2;i>=0;i--){
      for(int j=0;j<n;j++){
        if(dp[i][j]>0){continue;}
        bool ok=false;
        if(dp[i+1][j]>0){ok=true;}
        if(j>0 && dp[i+1][j-1]>0){ok=true;}
        if(j+1<n && dp[i+1][j+1]>0){ok=true;}
        if(ok){
          if(s[i][j]=='.'){
            dp[i][j]=1;
          }
          else{
            if(low[j]==i){
              for(int k=0;k<=i;k++){
                dp[k][j]=1;
              }
            }
          }
        }
      }
    }
    for(auto &nx : dp[0]){cout << nx;}
    cout << "\n";
  }
  return 0;
}