B - Putting Bricks in the Wall ～入口と出口なら管理しやすい～

• Quiz
  • https://codeforces.com/contest/1421/problem/B
• AC
  • https://codeforces.com/contest/1421/submission/96783516
• 解説
  • 左上を00で囲む、右下を11で囲むなどできれば到達不可能にできる
  • 左上を0,1のどちらで囲むか、右下を0,1のどちらで囲むかは初期状態を見て適切に選べば2回のswapで十分
  • こういうグリッドを見るとbfsしそうになるが不要だった

void solve(){
  ll N;
  cin>>N;
  VS S(N);
  rep(i,N)cin>>S[i];
  
  ll goal=0;
  if(S[N-1][N-2]=='1')goal++;
  if(S[N-2][N-1]=='1')goal++;

  ll start=0;
  if(S[0][1]=='1')start++;
  if(S[1][0]=='1')start++;

  vector<PII> Ans; // (y,x)
  if(goal==0){
    // 左上を1で囲む
    if(S[0][1]=='0')Ans.push_back({0,1});
    if(S[1][0]=='0')Ans.push_back({1,0});
  }
  else if(goal==2){
    // 左上を0で囲む
    if(S[0][1]=='1')Ans.push_back({0,1});
    if(S[1][0]=='1')Ans.push_back({1,0});
  }
  else{
    // goal==1
    if(start==0){
      // 右下を1で囲む
      if(S[N-1][N-2]=='0')Ans.push_back({N-1,N-2});
      if(S[N-2][N-1]=='0')Ans.push_back({N-2,N-1});
    }
    else if(start==2){
      // 右下を0で囲む
      if(S[N-1][N-2]=='1')Ans.push_back({N-1,N-2});
      if(S[N-2][N-1]=='1')Ans.push_back({N-2,N-1});
    }
    else{
      // start==1
      // 左上を0で囲み、右下を1で囲む
      // 左上を0で囲む
      if(S[0][1]=='1')Ans.push_back({0,1});
      if(S[1][0]=='1')Ans.push_back({1,0});
      // 右下を1で囲む
      if(S[N-1][N-2]=='0')Ans.push_back({N-1,N-2});
      if(S[N-2][N-1]=='0')Ans.push_back({N-2,N-1});
    }
  }
  p(SZ(Ans));
  for(auto pa : Ans){
    p2(pa.first+1, pa.second+1);
  }
}

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

    // input
    ll N; cin>>N;
    while(N--)solve();
    
    return 0;
}