Google Code Jam 2009, Qualification Round B Watersheds

//Google Code Jam 2009, Qualification Round B Watersheds

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

//Google Code Jam
public class GoogleCode1 {
    private static MyScanner in;
    private static PrintStream out;

    private static void solve() throws IOException
    {
        int C = in.nextInt();
        for (int i = 0; i < C; i++) {
            out.print("Case #" + (i + 1) + ":");
            solveCase();
        }
    }

    private static void solveCase() throws IOException {
        int H = in.nextInt();
        int W = in.nextInt();
        int[][] alt = new int[H + 2][W + 2];
        for (int i = 0; i <= H + 1; i++) {
            for (int j = 0; j <= W + 1; j++) {
                if (i == 0 || i == H + 1 || j == 0 || j == W + 1)
                    alt[i][j] = 10001;
                else
                    alt[i][j] = in.nextInt();
            }
        }
        char[][] basin = new char[H + 2][W + 2];
        for (int i = 0; i < H + 2; i++) {
            for (int j = 0; j < W + 2; j++) {
                basin[i][j] = '-';
            }
        }

        int cnt = 0;
        char lastbasin = 'a';
        while (cnt < W * H)
        {
            for (int i = 1; i <= H; i++) {
                for (int j = 1; j <= W; j++) {
                    if (basin[i][j] != '-')
                        continue;
                    int altc = alt[i][j];
                    int minAltN = altc;
                    minAltN = Math.min(minAltN, alt[i - 1][j]);
                    minAltN = Math.min(minAltN, alt[i + 1][j]);
                    minAltN = Math.min(minAltN, alt[i][j - 1]);
                    minAltN = Math.min(minAltN, alt[i][j + 1]);
                    if (altc == minAltN) {
                        basin[i][j] = lastbasin;
                        lastbasin++;
                        cnt++;
                    }
                    else {
                        if (alt[i - 1][j] == minAltN) {
                            basin[i][j] = basin[i - 1][j];
                        } else if (alt[i][j - 1] == minAltN) {
                            basin[i][j] = basin[i][j - 1];
                        } else if (alt[i][j + 1] == minAltN) {
                            basin[i][j] = basin[i][j + 1];
                        } else if (alt[i + 1][j] == minAltN) {
                            basin[i][j] = basin[i + 1][j];
                        }
                        if (basin[i][j] != '-')
                            cnt++;
                    }
                }
            }
        }

        // sort basins
        char[][] sortedbasin = new char[H + 2][W + 2];
        char lastchar = 'a';
        HashMap<Character, Character> map = new HashMap<>();
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                char b = basin[i][j];
                if (!map.containsKey(b)) {
                    map.put(b, lastchar);
                    lastchar++;
                }
                sortedbasin[i][j] = map.get(b);
            }
        }

        out.println();
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                out.print(sortedbasin[i][j]);
                out.print(" ");
            }
            out.println();
        }

    }

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean usingFileForIO = true;
        if (usingFileForIO) {
            // using input.txt and output.txt as I/O
            in = new MyScanner("E:\\zin.txt");
            out = new PrintStream("E:\\zout.txt");
        }
        else {
            in = new MyScanner();
            out = System.out;
        }

        solve();
    }

    // =====================================
    static class MyScanner {
        Scanner inp = null;

        public MyScanner() throws IOException
        {
            inp = new Scanner(System.in);
        }

        public MyScanner(String inputFile) throws IOException {
            inp = new Scanner(new FileInputStream(inputFile));
        }

        public int nextInt() throws IOException {
            return inp.nextInt();
        }

        public long nextLong() throws IOException {
            return inp.nextLong();
        }

        public double nextDouble() throws IOException {
            return inp.nextDouble();
        }

        public String nextString() throws IOException {
            return inp.next();
        }

        public String nextLine() throws IOException {
            return inp.nextLine();
        }
    }

}