Submission #1131279

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <istream>
#include <ostream>

#include <cstdlib>
#include <cmath>
#include <cstdio>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i,n) for(ll i=0; i < (n); ++i)
#define rrep(i,n) for(ll i=((n)-1); i >= 0; --i)

#define OPLT(T) bool operator<(const T & lop_, const T & rop_)
#define OPEQ(T) bool operator==(const T & lop_, const T & rop_)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

istream& operator>>(istream& istr, __float128& obj) { double d; istr >> d; obj = d; return istr; };
ostream& operator<<(ostream& ostr, __float128& obj) { ostr << static_cast<double>(obj); return ostr; };

int use[1<<10];

int main() {
	int N;
	cin >> N;
	vector<string> s(N);
	rep(i,N) cin >> s[i];
	if(N > 3) return 0;
	int a = 0;
	rep(i,N) {
		rep(j,N) {
			a *= 2;
			a += s[i][j] == '#';
		}
	}
	rep(i,1<<10) use[i] = -1;
	queue<int> q;
	q.push(a);
	use[a] = 0;
	while(q.size()) {
		a = q.front(); 
		int c[4][4];
		rep(i,N) {
			rep(j,N) {
				c[N-1-i][N-1-j] = a&1;
				a /= 2;
			}
		}
		a = q.front(); q.pop();

		rep(i,N) {
			rep(j,N) {
				int d[4][4];
				rep(k,N) {
					rep(l,N) {
						d[k][l] = c[k][l];
					}
				}
				rep(k,N) {
					d[k][j] = c[i][k];
				}
				int b = 0;
				rep(k,N) {
					rep(l,N) {
						b *= 2;
						b += d[k][l];
					}
				}
				if(use[b]+1) continue;
				use[b] = use[a]+1;
				q.push(b);
//				cout << a << " " << use[a] << " " << b << " " << use[b] << endl;
			}
		}
	}
	cout << use[(1<<(N*N))-1] << endl;
//	rep(i,(1<<(N*N))) cout << use[i] << " ";cout << endl;
	return 0;
}

Submission Info

Judge Result