Code Jam : Watersheds

Problem

Geologists sometimes divide an area of land into different regions based on where rainfall flows down to. These regions are called drainage basins.

Given an elevation map (a 2-dimensional array of altitudes), label the map such that locations in the same drainage basin have the same label, subject to the following rules.

* From each cell, water flows down to at most one of its 4 neighboring cells.
* For each cell, if none of its 4 neighboring cells has a lower altitude than the current cell's, then the water does not flow, and the current cell is called a sink.
* Otherwise, water flows from the current cell to the neighbor with the lowest altitude.
* In case of a tie, water will choose the first direction with the lowest altitude from this list: North, West, East, South.

Every cell that drains directly or indirectly to the same sink is part of the same drainage basin. Each basin is labeled by a unique lower-case letter, in such a way that, when the rows of the map are concatenated from top to bottom, the resulting string is lexicographically smallest. (In particular, the basin of the most North-Western cell is always labeled 'a'.)

Input

The first line of the input file will contain the number of maps, T. T maps will follow, each starting with two integers on a line -- H and W -- the height and width of the map, in cells. The next H lines will each contain a row of the map, from north to south, each containing W integers, from west to east, specifying the altitudes of the cells.

Output

For each test case, output 1+H lines. The first line must be of the form

Case #X:

where X is the test case number, starting from 1. The next H lines must list the basin labels for each of the cells, in the same order as they appear in the input.

Limits

T ≤ 100;

Small dataset

1 ≤ H, W ≤ 10;
0 ≤ altitudes < 10.
There will be at most two basins.

Large dataset

1 ≤ H, W ≤ 100;
0 ≤ altitudes < 10,000.
There will be at most 26 basins.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
/**
 * 
 * @author anuj.mehta
 */
public class Watersheds {
 private final static int UP = 1;
 private final static int DOWN = 2;
 private final static int LEFT = 3;
 private final static int RIGHT = 4;
 private final static int SELF = 5;
 private static boolean basinFound = false;
 private static char basinName = 'a';

 public static void findFirstBasin(int[][] dirInfoMap, int curRow, int curCol, char[][] basinInfoMap)
 {
  int dir = dirInfoMap[curRow][curCol];
  if(dir == SELF)
  {
   basinInfoMap[curRow][curCol] = basinName;
   basinFound = true;
   return;
  }
  switch (dir) {
   case UP:
    curRow--;
    break;
   case DOWN:
    curRow++;
    break;
   case LEFT:
    curCol--;
    break;
   case RIGHT:
    curCol++;
  }
  findFirstBasin(dirInfoMap, curRow, curCol, basinInfoMap);
  if(basinFound)
   basinInfoMap[curRow][curCol] = basinName;
 }
 
 public static char populateBasinNames(int[][] dirInfoMap, int curRow, int curCol, char[][] basinInfoMap)
 {
  int dir = dirInfoMap[curRow][curCol];
  switch(dir)
  {
  case SELF:
   char name = basinInfoMap[curRow][curCol];
   if(name == '\u0000')
   {
    basinName += 1;
    basinInfoMap[curRow][curCol] = basinName;
    return basinName;
   }
   else
    return name;
  case UP:
   curRow--;
   break;
  case DOWN:
   curRow++;
   break;
  case LEFT:
   curCol--;
   break;
  case RIGHT:
   curCol++;
  }
  return populateBasinNames(dirInfoMap, curRow, curCol, basinInfoMap);
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {
  try {
   BufferedReader br = new BufferedReader(new FileReader("Test.txt"));
   int numOfMaps = Integer.parseInt(br.readLine());
   for(int i =0; i < numOfMaps; i++)
   {
    basinName = 'a';
    String[] elevationMapDimensions = br.readLine().split(" ");
    int height = Integer.parseInt(elevationMapDimensions[0]);
    int width = Integer.parseInt(elevationMapDimensions[1]);
    int[][] elevationMap = new int[height][width];
    int[][] dirInfoMap = new int[height][width];
    //Store the altitude data in array
    for(int j = 0; j < height; j++)
    {
     String[] altitudeData = br.readLine().split(" ");
     for(int k = 0; k < width; k++)
     {
      elevationMap[j][k] = Integer.parseInt(altitudeData[k]);
     }
    }
    
    //Now process array elements
    for(int j =0; j < height; j++)
    {
     for(int k =0; k < width; k++)
     {
      int target = elevationMap[j][k];
      int left = -1, right = -1, up = -1, down = -1; 
      
      //get neighbours
      if(k-1 >= 0)
       left = elevationMap[j][k-1];
      if(k +1 < width)
       right = elevationMap[j][k+1];
      if(j-1 >= 0)
       up = elevationMap[j-1][k];
      if(j +1 < height)
       down = elevationMap[j+1][k];
      int small = target;
      int direction = SELF;
      if(up != -1 && up < target)
      {
       small = up;
       direction = UP;
      }
      if( left != -1 && left < target )
      {
       if(small == -2)
       { 
        small = left;
        direction = LEFT;
       }
       else if(left < small)
       {
        small = left;
        direction = LEFT;
       }
      }
      if( right != -1 && right < target )
      {
       if(small == -2)
       {
        small = right;
        direction = RIGHT;
       }
       else if(right < small)
       {
        small = right;
        direction = RIGHT;
       }
      }
      if( down != -1 && down < target )
      {
       if(small == -2)
       {
        small = down;
        direction = DOWN;
       }
       else if(down < small)
       {
        small = down;
        direction = DOWN;
       }
      }
      dirInfoMap[j][k] = direction;
     }
    }
    
    char[][] basinInfoMap = new char[height][width];
    int curRow = 0, curCol = 0;
    basinFound = false;
    //first find the first basin
    findFirstBasin(dirInfoMap, curRow, curCol, basinInfoMap);
    if(basinFound)
     basinInfoMap[curRow][curCol] = basinName;
    for(int row = 0; row < height; row++)
    {
     for(int col = 0; col < width; col++)
     {
      //populate rest of the basin info
      char name = populateBasinNames(dirInfoMap, row, col, basinInfoMap);
      basinInfoMap[row][col] = name;
     }
    }
    
    for(int j = 0; j < height; j++)
    {
     for(int k = 0; k < width; k++)
      System.out.print(basinInfoMap[j][k] + "\t");
     System.out.println();
    }
    System.out.println("================================");
   }
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  } catch (NumberFormatException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  }
 }

}