gistfile1.txt

import java.awt.*;
import java.util.*;
import java.util.List;

public class CopsAndRobbers {

    static long one = 1;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int c = in.nextInt();

        int[] colors = new int[c];
        for (int i = 0; i < colors.length; i++) {

        }

        char[][] graph = new char[n][m];

        in.nextLine();
        for (int i = 0; i < n; i++) {
            char[] line = in.nextLine().toCharArray();
            for (int j = 0; j < m; j++)
                graph[i][j] = line[j];
        }

        for (char[] row : graph) {
            System.out.println(Arrays.toString(row));
        }
        in.nextInt();

        MaxFlowSolver dinic = new Dinic(((n * m) - 4) * 4);
        Map<Point, List<Node>> map = new HashMap<>();
        List<Node> list = new ArrayList<Node>();
        Node sink = dinic.addNode();
        Point[][] points = new Point[n][m];
        list.add(sink);
        map.put(new Point(-1, -1), list);
        Node src = new Node();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char curr = graph[i][j];
                if ((i == 0 && j == 0) || (i == 0 && j == m - 1) || (i == n - 1 && j == 0) || (i == n - 1 && j == m - 1)) {
                    if (curr == 'B') {
                        System.out.println("-1");
                        return;
                    }
                    continue;
                }
                if (curr == 'B') {
                    src = dinic.addNode();

                    if (i > 0) {
                        Point p = points[i-1][j];
                        List<Node> other = map.get(p);
                        Node in2 = other.get(0);

                        dinic.link(src, in2, one, 0);
                    }
                    if (i < n - 1) {
                        Point p = points[i+1][j];
                        List<Node> other = map.get(p);
                        Node in2 = other.get(0);

                        dinic.link(src, in2, one, 0);
                    }
                    if (j > 0) {
                        Point p = points[i][j-1];
                        List<Node> other = map.get(p);
                        Node in2 = other.get(0);

                        dinic.link(src, in2, one, 0);
                    }
                    if (j < m - 1) {
                        Point p = points[i][j+1];
                        List<Node> other = map.get(p);
                        Node in2 = other.get(0);

                        dinic.link(src, in2, one, 0);
                        dinic.link(src, in2, one, 0);
                    }
                } else {
                    long cost = (curr == '.') ? Long.MAX_VALUE : colors['a' - curr];
                    Node in1 = dinic.addNode();
                    Node out = dinic.addNode();
                    dinic.link(in1, out, 1, cost);
                    List<Node> nodeList = new ArrayList<Node>();
                    nodeList.add(in1);
                    nodeList.add(out);

                    Point newPoint = new Point(i,j);
                    points[i][j] = newPoint;
                    map.put(newPoint, nodeList);
                    if (i > 0) {
                        if(graph[i-1][j] == 'B') continue;
                        Point p = points[i-1][j];
                        List<Node> other = map.get(p);
                        Node in2 = other.get(0);
                        Node out2 = other.get(1);

                        dinic.link(in1, out2, one, 0);
                        dinic.link(in2, out, one, 0);
                    }
                    if (i < n - 1) {
                        if(graph[i+1][j] == 'B') continue;
                        Point p = points[i+1][j];
                        List<Node> other = map.get(p);
                        Node in2 = other.get(0);
                        Node out2 = other.get(1);

                        dinic.link(in1, out2, one, 0);
                        dinic.link(in2, out, one, 0);
                    }
                    if (j > 0) {
                        if(graph[i][j-1] == 'B') continue;
                        Point p = points[i][j-1];
                        List<Node> other = map.get(p);
                        Node in2 = other.get(0);
                        Node out2 = other.get(1);

                        dinic.link(in1, out2, one, 0);
                        dinic.link(in2, out, one, 0);
                    }
                    if (j < m - 1) {
                        if(graph[i][j+1] == 'B') continue;
                        Point p = points[i][j+1];
                        List<Node> other = map.get(p);
                        Node in2 = other.get(0);
                        Node out2 = other.get(1);

                        dinic.link(in1, out2, one, 0);
                        dinic.link(in2, out, one, 0);
                    }

                    if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                        sink = map.get(new Point(-1, -1)).get(0);
                        dinic.link(out, sink, one, 0);
                    }
                }
            }


            sink = map.get(new Point(-1,-1)).get(0);
            long d = dinic.getMaxFlow(src, sink);
            if (d == Long.MAX_VALUE) {
                System.out.println("-1");
                return;
            }
            System.out.println(d);
        }
    }

    public static class Node {
        // thou shall not create nodes except through addNode()
        private Node() {
        }

        List<Edge> edges = new ArrayList<Edge>();
        int index;          // index in nodes array

        // The following fields are needed only if the respective solvers
        // are being used. We include them here for improved spatial locality.
        // To avoid unnecessary memory consumption, be sure to remove
        // those fields that aren't used by the solver you are using
        //
        int dist;           // PushRelabel, Dinic, and AhujaOrlin.
        boolean blocked;    // Dinic
    }

    public static class Edge {
        boolean forward; // true: edge is in original graph
        // false: edge is a backward edge
        Node from, to;   // nodes connected
        long flow;        // current flow
        final long capacity;
        Edge dual;      // reference to this edge's dual
        long cost;      // only used for MinCost.

        // thou shall not create edges except through link()
        protected Edge(Node s, Node d, long c, boolean f) {
            forward = f;
            from = s;
            to = d;
            capacity = c;
        }

        // remaining capacity()
        long remaining() {
            return capacity - flow;
        }

        // increase flow and adjust dual
        void addFlow(long amount) {
            flow += amount;
            dual.flow -= amount;
        }
    }

    /* A Max Flow solver base class. */
    public static abstract class MaxFlowSolver {
        /* List of nodes, indexed. */
        List<Node> nodes = new ArrayList<Node>();

        /* Create an edge between nodes n1 and n2 */
        public void link(Node n1, Node n2, long capacity) {
            /*
             * Only the EdmondsKarp solver takes cost into account
             * during getMaxFlow().  Setting it to 1 for problems
             * that do not involve cost means it uses a shortest path
             * search when finding augmenting paths.  In practice,
             * this does not seem to make a difference.
             */
            link(n1, n2, capacity, 1);
        }

        /* Create an edge between nodes n1 and n2 and assign cost */
        public void link(Node n1, Node n2, long capacity, long cost) {
            Edge e12 = new Edge(n1, n2, capacity, true);
            Edge e21 = new Edge(n2, n1, 0, false);
            e12.dual = e21;
            e21.dual = e12;
            n1.edges.add(e12);
            n2.edges.add(e21);
            e12.cost = cost;
            e21.cost = -cost;
        }

        /* Create an edge between nodes n1 and n2 */
        void link(int n1, int n2, long capacity) {
            link(nodes.get(n1), nodes.get(n2), capacity);
        }

        /* Create a graph with n nodes. */
        protected MaxFlowSolver(int n) {
            for (int i = 0; i < n; i++)
                addNode();
        }

        protected MaxFlowSolver() {
            this(0);
        }

        public abstract long getMaxFlow(Node src, Node snk);

        /* Add a new node. */
        public Node addNode() {
            Node n = new Node();
            n.index = nodes.size();
            nodes.add(n);
            return n;
        }
    }

    /**
     * Dinic's algorithm, Shimon Even variant.
     */
    public static class Dinic extends MaxFlowSolver {
        long BlockingFlow(Node src, Node snk) {
            int N = nodes.size();
            for (Node u : nodes) {
                u.dist = -1;
                u.blocked = false;
            }
            Node[] Q = new Node[N];

            /* Step 1.  BFS from source to compute levels */
            src.dist = 0;
            int head = 0, tail = 0;
            Q[tail++] = src;
            while (head < tail) {
                Node x = Q[head++];
                List<Edge> succ = x.edges;
                for (Edge e : succ) {
                    if (e.to.dist == -1 && e.remaining() > 0) {
                        e.to.dist = e.from.dist + 1;
                        Q[tail++] = e.to;
                    }
                }
            }

            if (snk.dist == -1)     // no flow if sink is not reachable
                return 0;

            /* Step 2. Push flow down until we have a blocking flow */
            long flow, totflow = 0;
            do {
                flow = dfs(src, snk, Long.MAX_VALUE);
                totflow += flow;
            } while (flow > 0);
            return totflow;
        }

        /*
         * Run DFS on the BFS level graph.
         */
        long dfs(Node v, Node snk, long mincap) {
            // reached sink
            if (v == snk)
                return mincap;

            for (Edge e : v.edges) {
                // standard DFS, but consider an edge only if
                if (!e.to.blocked    // the path to the sink is not already blocked
                        && e.from.dist + 1 == e.to.dist // it's in the BFS level graph
                        && e.remaining() > 0) {  // the edge has remaining capacity
                    long flow = dfs(e.to, snk, Math.min(mincap, e.remaining()));
                    if (flow > 0) {
                        e.addFlow(flow);
                        return flow;
                    }
                }
            }
            // if we couldn't add any flow then there is no point in ever going
            // past this node again.  Mark it blocked.
            v.blocked = true;
            return 0;
        }

        @Override
        public long getMaxFlow(Node src, Node snk) {
            long flow, totflow = 0;
            while ((flow = BlockingFlow(src, snk)) != 0)
                totflow += flow;
            return totflow;
        }

        public Dinic() {
            this(0);
        }

        public Dinic(int n) {
            super(n);
        }
    }
}