Google Code Jam Qualification Round 2009 (3)

広告

B問題: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.

Sample

Input
5
3 3
9 6 3
5 9 6
3 5 9
1 10
0 1 2 3 4 5 6 7 8 7
2 3
7 6 7
7 6 7
5 5
1 2 3 4 5
2 9 3 9 6
3 3 0 8 7
4 9 8 9 8
5 6 7 8 9
2 13
8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8

Output
Case #1:
a b b
a a b
a a a
Case #2:
a a a a a a a a a b
Case #3:
a a a
b b b
Case #4:
a a a a a
a a b b a
a b b b a
a b b b a
a a a a a
Case #5:
a b c d e f g h i j k l m
n o p q r s t u v w x y z

コメント

降水量の問題。雨が降り、一番低い隣接した部分に流れる。同じ高さがある場合は優先順位が北、西、東、南の順になる。現在の高さと隣の高さが同じときは流れない。これ以上流れる場所がない場所をsinkと言う。

雨が降って流れた先が同じsinkになるものは同じラベル(aとかbとか)をつける。

入力の最初の5は5つの問題があるという意味。次の3 3は3 x 3のマップですよという意味。続いて3 x 3のデータがある。その次が1 x 10のマップがありますという意味。以下同様。

ラベルをつけていったとき、どうなるかが出力。こういうのは手でやってみるとよい。

解いてみる

とりあえずトップダウン式とボトムアップ式が思いつく。ボトムアップは一番低いところから逆にどんどん遡っていく。sinkの数を先に決めてしまって、あとはどのsinkに属するか決めるだけなので楽のようだけど、遡れる箇所が1つじゃないので面倒だと思った。そういうわけで、トップダウン式にやることにする。

あまり計算量が多くなさそうなので、かなり雑に計算することに。まず、全てのマス目をsinkまでたどる。sinkの座標を適当に加工して他の値と重ならないように調整。本当はpoint(x, y)型のmapを用意すればいいのだけど、手抜きをした。その分ソースは汚くなっている。sinkを探すのは再帰でやってしまう。

全てのマス目のsinkの位置を計算して、同じsinkになっているところに同じラベルを貼る。

例によってごりごり書いた汚いコード。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//#define DEBUG


const int MAX_ALTITUDE = 10 - 1;
const int WALL = 0xffffff;


class matrix_2d
{
public:
	matrix_2d( int n, int m );
	~matrix_2d()
	{
		if( matrix != NULL )
		{
			delete [] matrix;
			matrix = NULL;
		}
	}
	
	int &operator()(int n, int m);
	
	int X(){
		return x;
	}

	int Y(){
		return y;
	}
	
	
private:
	int x;
	int y;
	int z;
	int *matrix;
};


matrix_2d::matrix_2d( int n, int m ) : matrix(NULL)
{
	x = n;
	y = m;
	
	matrix = new int[x*y];
	bzero( matrix, sizeof(int) * x * y );
}

int &matrix_2d::operator()(int n, int m)
{
	if( x * m + n > x * y )
	{
		puts("out of bound");
		return z;
	}
	
	return matrix[x * m + n];	
}





static void print_map( matrix_2d &map )
{
	int H = map.Y();
	int W = map.X();
	
	for( int y = 0; y < H; y++ )
	{
		for( int x = 0; x < W; x++ )
		{
			if( map(x,y) == WALL )
				printf("*");
			else if( 20000 <= map(x,y) && map(x,y) <= 20000 + 'z' )
				printf("%c", map(x,y) - 20000);
			else 
				printf("%d",map(x,y));
		}
		puts("");
	}
	puts("");
	puts("");
}


static void print_result( matrix_2d &map )
{
	int H = map.Y();
	int W = map.X();
	
	for( int y = 1; y < H - 1; y++ )
	{
		for( int x = 1; x < W - 1; x++ )
		{
			printf("%c ", map(x,y) );

		}
		puts("");
	}
}



static int determine_flow( matrix_2d &map, int x, int y )
{
	int current = map( x, y );
	int north = map( x, y - 1 );
	int west = map( x - 1, y );
	int east = map( x + 1, y );
	int south = map( x, y + 1 );


	// north
	if( north < current && north <= west && north <= east && north <= south )
		return determine_flow( map, x, y - 1 );
	
	// west
	if( west < current && west < north && west <= east && west <= south )
		return determine_flow( map, x - 1, y );

	// east
	if( east < current && east < west && east < north && east <= south )
		return determine_flow( map, x + 1, y );

	// south
	if( south < current && south < west && south < east && south < north )
		return determine_flow( map, x, y + 1 );
	
	// exit of recursive
	return x << 16 | y << 8;
}




static void each_map( FILE *in )
{
	char line[8192];
	int H, W;
	
	fgets( line, sizeof(line), in );
	sscanf( line, "%d %d", &H, &W );
	
#ifdef DEBUG
	printf( "H = %d, W = %dn", H, W );
#endif

	matrix_2d map( W + 2, H + 2 );
	matrix_2d map2( W + 2, H + 2 );

	// surround the map( altitude = WALL(32767) )
	for( int y = 0; y < H + 2; y++ )
	{
		map(0, y) = WALL;
		map(W+2-1, y) = WALL;		
		map2(0, y) = WALL;
		map2(W+2-1, y) = WALL;		
	}
	
	for( int x = 0; x < W + 2; x++ )
	{
		map(x, 0) = WALL;
		map(x, H+2-1) = WALL;
		map2(x, 0) = WALL;
		map2(x, H+2-1) = WALL;		
	}
	
	// set the map
	for( int y = 1; y < H + 2 - 1; y++ )
	{
		fgets( line, sizeof(line), in );
		char *l = line;
		
		for( int x = 1; x < W + 2 - 1; x++ )
		{
			int altitude = 0;
			while( true )
			{
				char c = *l++;
				
				if( '0' <= c && c <= '9' )
				{
					altitude *= 10;
					altitude += c - '0';				
					map(x, y) = altitude;
				}
				
				// space
				if( c == ' ' || c == '' || c == 0x0a )
					break;				
			}
		}
	}

#ifdef DEBUG
	print_map(map);
#endif
	
	// find basins
	for( int x = 1; x < W + 2 - 1; x++ )
		for( int y = 1; y < H + 2 - 1; y++ )
		{
			int point = determine_flow( map, x, y );
			int p_y = ( point >> 8 ) & 0xff;
			int p_x = point >> 16;

#ifdef DEBUG
			printf( "(%d,%d)->(%d,%d)n", x, y, p_x, p_y );
#endif
			
			
			map2( x, y ) = point;
		}
	
	char label = 'a';
	for( int x = 1; x < W + 2 - 1; x++ )
	{
		for( int y = 1; y < H + 2 - 1; y++ )
		{
			int current = map2( x, y );
			if( 'z' < current )
			{
				map2( x, y ) = label;

				for( int X = 1; X < W + 2 - 1; X++ )
					for( int Y = 1; Y < H + 2 - 1; Y++ )
					{
						if( map2( X, Y ) == current )
							map2( X, Y ) = label;
					}
				label++;
			}
					
		}
	}
	
	print_result(map2);
	
}


int main()
{
	char line[8192];
	FILE *input = fopen("input.txt","rt");
	int T;
	
	if( input == NULL )
	{
		puts("File not found.");
		return EXIT_FAILURE;		
	}
	
	fgets( line, sizeof(line), input );
	sscanf( line, "%d", &T);
	
	printf("There are %d maps in the problemn", T );
	
	for( int i = 0; i < T; i++ )
	{
		printf( "Case #%d:n", i + 1 );
		each_map(input);
	}	
}

手抜きのためにマップの外側を壁で囲んでおいた。壁の高さは非常に高く設定しておくと条件分岐が少し減る。

とりあえず、サンプルとsmall問題は通る。largeもさくっと答えが出たのでsubmit。