/* vim: set expandtab tabstop=4 shiftwidth=4 : */

class Board {

    private int d;
    private byte[][] blocks;
    private int openRow;
    private int openCol;

    private Board(byte[][] blocks, int openI, int openJ)
    {
        this.d = blocks[0].length;
        this.blocks = blocks;
        this.openRow = openI;
        this.openCol = openJ;
    }

    // construct a board from an N-by-N array of blocks
    // (where blocks[i][j] = block in row i, column j)
    public Board(int[][] blocks)
    {

        this.d = blocks[0].length;
        this.openRow = this.d - 1;
        this.openCol = this.d - 1;
        this.blocks = new byte[d][d];

        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++)
                this.blocks[i][j] = (byte) blocks[i][j];
    }

    // board dimension N
    public int dimension()
    {
        return d;
    }

    // number of blocks out of place
    public int hamming()
    {
        int k = 1;
        int hamming = 0;

        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++, k++)
                if (blocks[i][j] != 0 && blocks[i][j] != k) hamming += 1;

        return hamming;
    }

    // sum of Manhattan distances between blocks and goal
    public int manhattan()
    {
        int manhattan = 0;

        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++)
            {
                int v = blocks[i][j] -1;
                if (v == -1) continue;
                manhattan += Math.abs((v / d) - i) + Math.abs((v % d) - j);
            }

        return manhattan;
    }

    // is this board the goal board?
    public boolean isGoal()
    {
        int k = 1;

        if (blocks[d-1][d-1] != 0) return false;

        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++)
                if (blocks[i][j] != k++ && !((i == j) && (j == d - 1))) return false;

        return true;
    }

    private Board swap(int r0, int c0, int r1, int c1)
    {
        byte[][] blocks2 = new byte[d][d];

        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++)
                blocks2[i][j] = blocks[i][j];

        byte tmp = blocks2[r0][c0];
        blocks2[r0][c0] = blocks2[r1][c1];
        blocks2[r1][c1] = tmp;

        return new Board(blocks2, openRow, openCol);
    }

    // a board obtained by exchanging two adjacent blocks in the same row
    public Board twin()
    {
        int row = 0;
        if (openRow == 0) row = 1;

        return swap(row, 0, row, 1);
    }

    // does this board equal y?
    public boolean equals(Object y)
    {
        if (y == null) return false;
        if (y.getClass() != this.getClass()) return false;

        Board other = (Board) y;

        if (d != other.dimension()) return false;
        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++)
                if (blocks[i][j] == other.blocks[i][j]) return true;
        return false;
    }

    // all neighboring boards
    public Iterable<Board> neighbors()
    {
        Queue<Board> q = new Queue<Board>();
        if (openRow != 0)
            q.enqueue(swap(openRow, openCol, openRow - 1, openCol));
        if (openRow < d - 1)
            q.enqueue(swap(openRow, openCol, openRow + 1, openCol));
        if (openCol != 0)
            q.enqueue(swap(openRow, openCol, openRow, openCol - 1));
        if (openCol < d - 1)
            q.enqueue(swap(openRow, openCol, openRow, openCol + 1));

        return q;
    }

    // string representation of the board
    public String toString()
    {
        String out = "";
        for (int i = 0; i < d; i++)
        {
            for (int j = 0; j < d; j++)
                out += " "+(int) blocks[i][j];
            out += "\n";
        }
        // out += "goal      "+(isGoal() ? "OK" : "KO")+"\n";
        // out += "hamming   "+hamming()+"\n";
        // out += "manhattan "+manhattan()+"\n";
        return out;
    }
}