11094 - Continents

[brianfry713]

From uhunt:
AKJ88> Hal shod, moshkel sare in bood ke mahale feli shoroo ro nabayad shemord. AC: http://ideone.com/5nJd4a

[faraa_T]

Hello
I tried many inputs but I get WA yet.
Plz help me...
Tnx

Code: Select all

Removed After AC :)

[arkidd]

i've passed all the testcases here but still got WA.
can somebody help me pls?

thanks

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int m, n, x, y, i, j, k;
int parent[10005];
char s[105][105];

int sum[10005];

int ans;

int dirx[] = {0,0,1,-1};
int diry[] = {1,-1,0,0};

char LAND;

int getid(int a, int b)
{
	return a * m + b;
}

int getparent(int a)
{
	return (parent[a] == a)? a : (parent[a] = getparent(parent[a]));
}

void unionset(int a, int b)
{
	parent[getparent(a)] = getparent(b);
}


int main()
{
	while (scanf("%d %d", &m, &n) != EOF)
	{
		for (i = 0; i < m; ++i)
			scanf("%s", s[i]);
		
		scanf("%d %d", &x, &y);
		
		LAND = s[x][y];
		
		// reset parent
		for (i = 0; i < m; ++i)
			for (j = 0; j < n; ++j)
			{	
				int id = getid(i,j);
				
				parent[id] = id;
			}
		
		// union parents
		for (i = 0; i < m; ++i)
		{
			for (j = 0; j < n; ++j)
			{
				if (s[i][j] != LAND) continue;
				
				int id = getid(i,j);
				
				for (k = 0; k < 4; ++k)
				{
					int nx = i+dirx[k], ny = (j+diry[k])%n;
										
					if (nx >= 0 && nx < m)
					{
						if (s[nx][ny] == LAND)
						{
							unionset(id, getid(nx,ny));
						}
					}
				}
			}
		}
		
		// count continents
		memset(sum, 0, sizeof(sum));
		for (i = 0; i < m; ++i)
			for (j = 0; j < n; ++j)
			{
				if (s[i][j] == LAND) sum[getparent(getid(i,j))]++;
			}
				
		// find answer
		ans = 0;
		for (i = 0; i < m; ++i)
		{
			for (j = 0; j < n; ++j)
			{				
				if (s[i][j] == LAND)
				if (getparent(getid(i,j)) != getparent(getid(x,y)))
					ans = max(ans, sum[getparent(getid(i,j))]);
			}
		}
		
		printf("%d\n", ans);
	}
	return 0;
}

[brianfry713]

Change line 22 to:
return a * n + b;

[RocknJon]

Hi guys, i try almost every test case in this forum and got the correct result all the time, but my Uva keep sending me wrong answer, please if someone could tell what is going on I will appreciate it. Thank you.

Code: Select all

#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;
char M[25][25];
bool Visit[25][25];

typedef stack<int> Si;
int m,n;
int cont;
char land,water;

void FirstDFS(int first,int second)
{
	if(second>=n)
		second = 0;
	if(second<0)
		second = n-1;
	if(first>=m || first<0)
		return;
	if(M[first][second]!=land)
		return;

	M[first][second]=water;

	FirstDFS(first+1,second);
	FirstDFS(first-1,second);
	FirstDFS(first,second-1);
	FirstDFS(first,second+1);

}

void SecondDFS(int first,int second)
{
	if(second>=n)
		second = 0;
	if(second<0)
		second = n-1;
	if(first>=m || first<0)
		return;
	if(M[first][second]!=land)
		return;

	M[first][second]=water;
	cont++;

	SecondDFS(first,second-1);
	SecondDFS(first,second+1);
	SecondDFS(first+1,second);
	SecondDFS(first-1,second);
}


int main()
{
	int x,y;
    while(scanf("%d %d\n",&m,&n)==2)
	{
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				scanf(" %c",&M[i][j]);
			}
		}
		

		scanf("%d %d\n\n",&x,&y);
		land = M[x][y];
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if(M[i][j]!=land)
					water = M[i][j];
			}
		}


		FirstDFS(x,y);
		int max=0;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(M[i][j]!=water)
				{
					cont=0;
					SecondDFS(i,j);
					if(cont>max)
						max=cont;
				}
				
			}		
		}
		printf("%d\n",max);
	}
    return 0;
}

[brianfry713]

Try input:

Code: Select all

3 3
l--
---
---
0 0

3 3
---
---
---
0 0

[garbage]

Removed

[brianfry713]

Don't print blank lines in the output.

[garbage]

It's showing RE. But why???

[brianfry713]

Post your updated code that doesn't print blank lines.

[garbage]

Code: Select all

Removed

[brianfry713]

Try the I/O in this thread.

[garbage]

Code: Select all

Accepted... :)

[uDebug]

I've culled all the great test cases on this thread and put them up here:

http://www.udebug.com/UVa/11094