Submission #1131237

---

Source Code Expand

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const ld EPS = 1e-8;

int dfs(vector<string> &a, int K) {
  int N = a.size();
  bool flag = true;
  REP(i,N)REP(j,N) if(a[i][j] == '.') flag = false;
  if(flag) return 0;

  if(K <= 0) return INF;

  int res = INF;

  REP(i,N)REP(j,N) {
    vector<string> cdd = a;
    REP(k,N) cdd[k][j] = a[i][k];
    res = min(res, 1 + dfs(cdd, K - 1));
  }
  return res;
}

int solve(vector<string> &a) {
  int N = a.size();

  bool flag = false;
  REP(i,N)REP(j,N) if(a[i][j] == '#') flag = true;
  if(!flag) return -1;

  return dfs(a, 2 * N);
}

int main(){
  int N;
  cin >> N;
  vector<string> a(N);
  REP(i,N) cin >> a[i];

  cout << solve(a) << endl;
  return 0;
}

Submission Info

Judge Result