Qualification Round 2009 Watersheds 迭代实现

原题：https://code.google.com/codejam/contest/90101/dashboard#s=p1&a=1

这道题目其实很简单，迭代就行了。大言不惭地说，迭代我最在行了。以前写过泡泡堂的地图引擎，比这个复杂多了。只要不StackOverflow，完全没问题。

思路很简单，两个二维数组，一个存海拔，一个存标签。遍历海拔数组，迭代流动，稍微有点麻烦的是方向的优先级，不过这也是小儿科了。最终的代码：

#include <iostream>
#include <vector>
using namespace std;
///////////////////////////SubMain//////////////////////////////////

void sink(const vector<vector<int> >& emap, int& m, int& n)
{
	int H = emap.size();
	int W = emap[0].size();

	// 排序找出最低的方向
	int nHeight = emap[n][m];
	int direction = 0;
	if(n + 1 < H && nHeight > emap[n + 1][m])	 // 再尝试下南
	{
		 nHeight = emap[n + 1][m];
		 direction = 1;
	}
	if(m + 1 < W && nHeight >= emap[n][m + 1])	 // 再尝试右东
	{
		nHeight = emap[n][m + 1];
		direction = 2;
	}
	if(m - 1 >= 0 && nHeight >= emap[n][m - 1])	 // 再尝试左西
	{
		nHeight = emap[n][m - 1];
		direction = 4;
	}
	if (n - 1 >= 0 && nHeight >= emap[n - 1][m])		 // 先尝试往上北流
	{
		nHeight = emap[n - 1][m];
		direction = 3;
	}
	if (nHeight == emap[n][m])
	{
		direction = 0;
	}
	
	switch(direction)
	{
	case 1:
		n = n + 1;
		break;
	case 2:
		m = m + 1;
		break;
	case 3:
		n = n - 1;
		break;
	case 4:
		m = m - 1;
		break;
	default:
		return;
	}
	sink(emap, m, n);
}

void solve(const vector<vector<int> >& emap, vector<vector<char> >& lmap)
{
	int H = emap.size();
	int W = emap[0].size();
	char c = 'a';
	for (int y = 0; y < H; y++)
	{
		for (int x = 0; x < W; x++)
		{
			int m = x;
			int n = y;
			sink(emap, m, n);
			if (lmap[n][m] == '*')
			{
				lmap[n][m] = c;
				c++;
			}
			lmap[y][x] = lmap[n][m];
		}
	}
}


int main(int argc, char *argv[])
{
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	int nCases = 0;
	cin >> nCases;
	cin.get();
	for (int i = 0; i < nCases; i++)
	{
		int H = 0; int W = 0;
		cin >> H >> W;
		vector<vector<int> > emap(H, vector<int>(W));
		vector<vector<char> > lmap(H, vector<char>(W));
		for (int y = 0; y < H; y++)
		{
			for (int x = 0; x < W; x++)
			{
				cin >> emap[y][x];
				lmap[y][x] = '*';
			}
		}
		
		solve(emap, lmap);
		cout << "Case #" << i + 1 << ": ";
		cout << endl;
		for (int y = 0; y < H; y++)
		{
			for (int x = 0; x < W; x++)
			{
				cout << lmap[y][x] << " ";
			}
			cout << endl;
		}
	}
	fclose(stdin);
	fclose(stdout);
	/*system("out.txt");*/
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » Qualification Round 2009 Watersheds 迭代实现