放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

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 迭代实现

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机