Submission #1131211

---

Source Code Expand

using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using Enu = System.Linq.Enumerable;

public class Program
{
    static readonly int INF = (int)1e9;
    int N;

    public void Solve()
    {
        N = Reader.Int();
        if (N > 3) throw new Exception();
        var grid = Reader.StringArray(N).Select(r => r.ToCharArray()).ToArray();
        int ans = BFS(grid);
        Console.WriteLine(ans == INF ? -1 : ans);
    }

    private int BFS(char[][] grid)
    {
        var set = new HashSet<int>();
        int initialMask = 0;
        for (int r = 0; r < N; r++)
            for (int c = 0; c < N; c++)
                initialMask |= ".#".IndexOf(grid[r][c]) << (r * N + c);
        set.Add(initialMask);
        int want = (1 <<  N * N) -1;

        for (int steps = 0; steps < 8; steps++)
        {
            var nset = new HashSet<int>();
            foreach (int g in set)
            {
                if (g == want) return steps;
                for (int selR = 0; selR < N; selR++)
                    for (int selC = 0; selC < N; selC++)
                    {
                        var nextg = g;
                        for (int i = 0; i < N; i++)
                        {
                            nextg &= ~(1 << (i * N + selC));
                            nextg |= (g >> (selR * N + i) & 1) << (i * N + selC);
                        }
                        nset.Add(nextg);
                    }
            }
            set = nset;
        }

        return INF;
    }
}


class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
    static TextReader reader = Console.In;
    static readonly char[] separator = { ' ' };
    static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
    static string[] A = new string[0];
    static int i;
    static void Init() { A = new string[0]; }
    public static void Set(TextReader r) { reader = r; Init(); }
    public static void Set(string file) { reader = new StreamReader(file); Init(); }
    public static bool HasNext() { return CheckNext(); }
    public static string String() { return Next(); }
    public static int Int() { return int.Parse(Next()); }
    public static long Long() { return long.Parse(Next()); }
    public static double Double() { return double.Parse(Next()); }
    public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
    public static int[] IntArray(int N) { return Range(N, Int); }
    public static int[][] IntTable(int H) { return Range(H, IntLine); }
    public static string[] StringArray(int N) { return Range(N, Next); }
    public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
    public static string Line() { return reader.ReadLine().Trim(); }
    public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
    static string[] Split(string s) { return s.Split(separator, op); }
    static string Next() { CheckNext(); return A[i++]; }
    static bool CheckNext()
    {
        if (i < A.Length) return true;
        string line = reader.ReadLine();
        if (line == null) return false;
        if (line == "") return CheckNext();
        A = Split(line);
        i = 0;
        return true;
    }
}

Submission Info

Judge Result