Submission #1131215

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<string> vs;
typedef pair<int,vs> P;
signed main(){
  int n;
  cin>>n;
  vs s(n);
  for(int i=0;i<n;i++) cin>>s[i];
  if(n>3) return 0;
  bool f=0;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      f|=s[i][j]=='#';
  if(!f){
    cout<<-1<<endl;
    return 0;
  }
  int ans=1000;
  queue<P> q;
  q.push(P(0,s));
  set<vs> sv;
  while(!q.empty()){
    P p=q.front();q.pop();
    int d=p.first;
    vs t=p.second;
    if(sv.count(t)) continue;
    sv.insert(t);
    bool ff=1;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
	ff&=t[i][j]=='#';
    if(ff){
      ans=d;
      break;
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	vs nx=t;
	for(int k=0;k<n;k++) nx[k][j]=t[i][k];
	q.push(P(d+1,nx));
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result