/******************************************************************/
/* ACM ICPC 2012-2013                                             */
/* Northeastern European Regional Contest                         */
/* St Petersburg - Barnaul - Tashkent - Tbilisi, December 2, 2012 */
/******************************************************************/
/* Problem A. Addictive Bubbles                                   */
/*                                                                */
/* Original idea         Georgiy Korneev                          */
/* Problem statement     Georgiy Korneev                          */
/* Test set              Georgiy Korneev                          */
/******************************************************************/
/* Checker                                                        */
/*                                                                */
/* Author                Georgiy Korneev                          */
/******************************************************************/

import ru.ifmo.testlib.Checker;
import ru.ifmo.testlib.InStream;
import ru.ifmo.testlib.Outcome;
import java.util.Arrays;
import static ru.ifmo.testlib.Outcome.Type.*;

public class Check implements Checker {

    void dfs(char[][] board, char v, int i, int j) {
        if (i < 0 || board.length <= i || j < 0 || board[i].length <= j || board[i][j] != v) {
            return;
        }
        board[i][j] = ' ';
        dfs(board, v, i + 1, j);
        dfs(board, v, i - 1, j);
        dfs(board, v, i, j + 1);
        dfs(board, v, i, j - 1);
    }

    void fall(char[][] b) {
        int[] c = new int[b[0].length];
        for (int i = b.length - 1; 0 <= i; i--) {
            for (int j = 0; j < b[i].length; j++) {
                if (b[i][j] == ' ') {
                    c[j]++;
                } else if (c[j] != 0) {
                    b[i + c[j]][j] = b[i][j];
                    b[i][j] = ' ';
                }
            }
        }
    }

    void compress(char[][] b) {
        int c = 0;
        for (int j = 0; j < b[0].length; j++) {
            boolean empty = true;
            for (int i = 0; i < b.length; i++) {
                empty &= b[i][j] == ' ';
            }
            if (empty) {
                c++;
            } else if (c != 0) {
                for (int i = 0; i < b.length; i++) {
                    b[i][j - c] = b[i][j];
                    b[i][j] = ' ';
                }
            }
        }
    }

    boolean play(char[][] board, int n) {
        char[][] b = new char[board.length][];
        boolean[] u = new boolean[n];
        boolean f = false;
        for (int i = 0; i < board.length; i++) {
            loop: for (int j = 0; j < board[i].length; j++) {
                char v = board[i][j];
                if (v < '1' || '1' + n <= v || u[v - '1']) {
                    continue;
                }
                u[v - '1'] = true;
                f = true;

                for (int r = 0; r < board.length; r++) {
                    b[r] = Arrays.copyOf(board[r], board[r].length);
                }
                dfs(b, v, i, j);
                for (char[] row : b) {
                    for (char c : row) {
                        if (c == v) {
                            continue loop;
                        }
                    }
                }
                fall(b);
                compress(b);
                if (play(b, n)) {
                    return true;
                }
            }
        }
        return !f;
    }

    public Outcome test(InStream inf, InStream ouf, InStream ans) {
        int h = inf.nextInt();
        int w = inf.nextInt();
        int z = inf.nextInt();
        int[] blueprint = new int[z];
        for (int i = 0; i < z; i++) {
            blueprint[i] = inf.nextInt();
        }

        char[][] board = new char[h][];
        int[] counts = new int[blueprint.length];
        for (int i = 0; i < h; i++) {
            board[i] = ouf.nextLine().trim().toCharArray();
            if (board[i].length != w) {
                throw new Outcome(PE, String.format("Row %d has %d bubbles instead of %d", i + 1, board[i].length, w));
            }
            for (char c : board[i]) {
                if (c < '1' || '1' + blueprint.length <= c) {
                    throw new Outcome(PE, String.format("Invalid color '%c'", c));
                }
                counts[c - '1']++;
            }
        }
        if (!ouf.seekEoF())
            throw new Outcome(PE, String.format("Extra data in output file"));

        for (int i = 0; i < blueprint.length; i++) {
            if (counts[i] != blueprint[i]) {
                throw new Outcome(WA, String.format("%d bubbles of color %d expected, %d found", blueprint[i], i, counts[i]));
            }
        }

        if (!play(board, blueprint.length)) {
            throw new Outcome(WA, String.format("Cannot remove all bubbles"));
        }
        return new Outcome(OK, String.format(""));
    }
}

