Submission #1131283

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 0x3fffffff;

int N;
map<vector<string>, int> memo;
int dfs(vector<string> &a){
	if( memo.count(a) ) return memo[a];
	memo[a] = INF;
	int ret = INF;
	rep(i,N) rep(j,N){
		vector<string> b = a;
		rep(k,N) b[k][j] = a[i][k];
		chmin( ret, dfs(b) + 1 );
	}
	return memo[a] = ret;
}

int main(){
	//ios_base::sync_with_stdio(0);

	cin >> N;
	vector<string> a(N);
	rep(i,N) cin >> a[i];

	vector<string> b(N);
	rep(i,N) rep(j,N) b[i] += "#";
	memo[b] = 0;

	int ans = dfs(a);
	if( ans == INF ) ans = -1;
	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result