import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class GameState {

    final static int[] DX = {-1, 0, 1, 0};
    final static int[] DY = {0, -1, 0, 1};

    public static enum Cell {
        FREE, GOOD, BAD
    }

    int n, m;
    Cell[][] field;

    public GameState(int n, int m) {
        this.n = n;
        this.m = m;
        field = new Cell[n][m];
        for (Cell[] xf : field) {
            Arrays.fill(xf, Cell.FREE);
        }
        field[0][0] = field[n - 1][m - 1] = Cell.GOOD;
    }

    public void set(int x, int y, Cell c) {
        field[x][y] = c;
    }

    boolean isWinningPositionForBadGuys() {
        boolean[][] used = new boolean[n][m];
        int[][] color = new int[n][m];
        for (int[] xc : color) {
            Arrays.fill(xc, -1);
        }
        int colors = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (used[i][j] || field[i][j] == Cell.BAD) {
                    continue;
                }
                if (field[i][j] == Cell.FREE) {
                    used[i][j] = true;
                    color[i][j] = colors++;
                } else {
                    Queue<Integer> q = new ArrayDeque<>();
                    q.add(i);
                    q.add(j);
                    used[i][j] = true;
                    color[i][j] = colors;
                    while (!q.isEmpty()) {
                        int x = q.poll();
                        int y = q.poll();
                        for (int d = 0; d < 4; d++) {
                            int xTo = x + DX[d];
                            int yTo = y + DY[d];
                            if (!(0 <= xTo && xTo < n) || !(0 <= yTo && yTo < m)) {
                                continue;
                            }
                            if (!used[xTo][yTo] && field[xTo][yTo] == Cell.GOOD) {
                                q.add(xTo);
                                q.add(yTo);
                                used[xTo][yTo] = true;
                                color[xTo][yTo] = colors;
                            }
                        }
                    }
                    colors++;
                }
            }
        }
        boolean[][] a = new boolean[colors][colors];
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                int c1 = color[x][y];
                if (c1 == -1) {
                    continue;
                }
                for (int d = 0; d < 4; d++) {
                    int xTo = x + DX[d];
                    int yTo = y + DY[d];
                    if (!(0 <= xTo && xTo < n) || !(0 <= yTo && yTo < m)) {
                        continue;
                    }
                    int c2 = color[xTo][yTo];
                    if (c2 == -1) {
                        continue;
                    }

                    if (c1 != c2) {
                        a[c1][c2] = true;
                    }
                }
            }
        }

        Queue<Integer> q = new ArrayDeque<>();
        q.add(color[0][0]);
        int[] d = new int[colors];
        Arrays.fill(d, -1);
        while (!q.isEmpty()) {
            int v = q.poll();
            for (int to = 0; to < colors; to++) {
                if (!a[v][to]) {
                    continue;
                }
                if (d[to] == -1) {
                    d[to] = d[v] + 1;
                    q.add(to);
                }
            }
        }

        int emptyCells = 0;
        for (Cell[] xc : field) {
            for (Cell c : xc) {
                emptyCells += c == Cell.FREE ? 1 : 0;
            }
        }

        int cFin = color[n - 1][m - 1];
        if (d[cFin] == -1) {
            return true;
        }
        return d[cFin] > emptyCells / 2;
    }

    public Graph toGraph() {
        boolean[][] used = new boolean[n][m];
        int[][] color = new int[n][m];
        for (int[] xc : color) {
            Arrays.fill(xc, -1);
        }
        int colors = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (used[i][j] || field[i][j] == Cell.BAD) {
                    continue;
                }
                if (field[i][j] == Cell.FREE) {
                    used[i][j] = true;
                    color[i][j] = colors++;
                } else {
                    Queue<Integer> q = new ArrayDeque<>();
                    q.add(i);
                    q.add(j);
                    used[i][j] = true;
                    color[i][j] = colors;
                    while (!q.isEmpty()) {
                        int x = q.poll();
                        int y = q.poll();
                        for (int d = 0; d < 4; d++) {
                            int xTo = x + DX[d];
                            int yTo = y + DY[d];
                            if (!(0 <= xTo && xTo < n) || !(0 <= yTo && yTo < m)) {
                                continue;
                            }
                            if (!used[xTo][yTo] && field[xTo][yTo] == Cell.GOOD) {
                                q.add(xTo);
                                q.add(yTo);
                                used[xTo][yTo] = true;
                                color[xTo][yTo] = colors;
                            }
                        }
                    }
                    colors++;
                }
            }
        }
        int[][] a = new int[colors][colors];
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                int c1 = color[x][y];
                if (c1 == -1) {
                    continue;
                }
                for (int d = 0; d < 4; d++) {
                    int xTo = x + DX[d];
                    int yTo = y + DY[d];
                    if (!(0 <= xTo && xTo < n) || !(0 <= yTo && yTo < m)) {
                        continue;
                    }
                    int c2 = color[xTo][yTo];
                    if (c2 == -1) {
                        continue;
                    }

                    if (c1 != c2) {
                        a[c1][c2]++;
                    }
                }
            }
        }
        Graph g = new Graph(colors);
        for (int i = 0; i < colors; i++) {
            for (int j = 0; j < colors; j++) {
                if (a[i][j] != 0) {
                    g.addEdge(i, j, a[i][j]);
                }
            }
        }
        g.defaultS = color[0][0];
        g.defaultT = color[n - 1][m - 1];
        return g;
    }
}
