Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个0MS的

Posted by raomeng at 2010-11-29 11:28:21 on Problem 1175
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;

int w, h;
char m[100][101];
char cord[320];
int cord_pos;

map<float, char> hash;

void dps(int x, int y)
{
	m[y][x] = '0';
	cord[cord_pos++] = x;
	cord[cord_pos++] = y;
	if (x > 0)
	{
		if (y > 0 && m[y-1][x-1] == '1')
			dps(x-1, y-1);
		if (m[y][x-1] == '1')
			dps(x-1, y);
		if (y < h-1 && m[y+1][x-1] == '1')
			dps(x-1, y+1);
	}
	if (y > 0 && m[y-1][x] == '1')
		dps(x, y-1);
	if (y < h-1 && m[y+1][x] == '1')
		dps(x, y+1);
	if (x < w-1)
	{
		if (y > 0 && m[y-1][x+1] == '1')
			dps(x+1, y-1);
		if (m[y][x+1] == '1')
			dps(x+1, y);
		if (y < h-1 && m[y+1][x+1] == '1')
			dps(x+1, y+1);
	}
}

int main()
{
	scanf("%d%d", &w, &h);
	for (int i = 0; i < h; ++i)
	{
		scanf("%s", m[i]);
	}
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			if (m[i][j] == '1')
			{
				cord_pos = 0;
				dps(j, i);
				double hash_code = 0.0;
				for (int k = 2; k < cord_pos; k += 2)
				{
					for (int l = 0; l < k; l += 2)
					{
						int tmp = cord[k+1] - cord[l+1];
						tmp *= tmp;
						tmp += (cord[k] - cord[l]) * (cord[k] - cord[l]);
						hash_code += sqrt((double)tmp);
					}
				}
				
				char& letter = hash[hash_code];
				if (!letter)
				{
					letter = 'a' + hash.size() - 1;
				}
				for (int k = 0; k < cord_pos; k += 2)
				{
					m[cord[k+1]][cord[k]] = letter;
				}
			}
		}
	}
	for (int i = 0; i < h; ++i)
	{
		printf("%s\n", m[i]);
	}
	
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator