Submission #1131248

---

Source Code Expand

// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define error(args...) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

int N;
int encode(bool state[3][3]) {
    int s = 0;
    REP(i, N) REP(j, N) {
        s = s << 1 | (state[i][j] ? 1 : 0);
    }
    return s;
}
void decode(int s, bool state[3][3]) {
    for(int i = N-1; i >= 0; i--) {
        for(int j = N-1; j >= 0; j--) {
            state[i][j] = (s & 1);
            s >>= 1;
        }
    }
}

int main(){
    iostream_init();
    while(cin >> N) {
        assert(N <= 3);
        bool grid[3][3] = {};
        REP(i, N) {
            string s;
            cin >> s;
            REP(j, N) {
                grid[i][j] = s[j] == '#';
            }
        }
        queue<int> que;
        int dist[1 << 10] = {};
        int start = encode(grid);
        memset(dist, -1, sizeof(dist));
        dist[start] = 0;
        que.push(start);
        int ans = -1;
        while(!que.empty()) {
            int s = que.front(); que.pop();
            bool state[3][3];
            decode(s, state);
            bool ok = true;
            REP(i, N) REP(j, N) if(!state[i][j]) ok = false;
            if(ok) {
                ans = dist[s];
                break;
            }
            REP(i, N){
                REP(j, N) {
                    bool nstate[3][3] = {};
                    REP(x, N) REP(y, N) nstate[y][x] = state[y][x];

                    bool d[3] = {};
                    REP(k, N) d[k] = state[i][k];

                    REP(k, N) {
                        nstate[k][j] = d[k];
                    }

                    int ns = encode(nstate);
                    if(dist[ns] == -1) {
                        dist[ns] = dist[s] + 1;
                        que.push(ns);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Submission Info

Judge Result