11094 - Continents

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11094 - Continents

Post by brianfry713 »

From uhunt:
AKJ88> Hal shod, moshkel sare in bood ke mahale feli shoroo ro nabayad shemord. AC: http://ideone.com/5nJd4a
Check input and AC output for thousands of problems on uDebug!

faraa_T
New poster
Posts: 8
Joined: Fri Jul 19, 2013 6:16 pm

Re: 11094 - Continents

Post by faraa_T »

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

Code: Select all

Removed After AC :)

arkidd
New poster
Posts: 3
Joined: Wed Aug 21, 2013 1:41 pm

Re: 11094 - Continents

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11094 - Continents

Post by brianfry713 »

Change line 22 to:
return a * n + b;
Check input and AC output for thousands of problems on uDebug!

RocknJon
New poster
Posts: 2
Joined: Sat Sep 27, 2014 12:12 am

Re: 11094 - Continents

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11094 - Continents

Post by brianfry713 »

Try input:

Code: Select all

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

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

Check input and AC output for thousands of problems on uDebug!

garbage
New poster
Posts: 19
Joined: Thu Feb 21, 2013 5:46 am

Re: 11094 - Continents, What's wrong???

Post by garbage »

Removed
Last edited by garbage on Sun Mar 01, 2015 7:43 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11094 - Continents

Post by brianfry713 »

Don't print blank lines in the output.
Check input and AC output for thousands of problems on uDebug!

garbage
New poster
Posts: 19
Joined: Thu Feb 21, 2013 5:46 am

Re: 11094 - Continents

Post by garbage »

It's showing RE. But why???

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11094 - Continents

Post by brianfry713 »

Post your updated code that doesn't print blank lines.
Check input and AC output for thousands of problems on uDebug!

garbage
New poster
Posts: 19
Joined: Thu Feb 21, 2013 5:46 am

Re: 11094 - Continents, RE???

Post by garbage »

Code: Select all

Removed
Last edited by garbage on Sun Mar 01, 2015 7:42 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11094 - Continents

Post by brianfry713 »

Try the I/O in this thread.
Check input and AC output for thousands of problems on uDebug!

garbage
New poster
Posts: 19
Joined: Thu Feb 21, 2013 5:46 am

Re: 11094 - Continents, WA??? Pls Help... :(

Post by garbage »

Code: Select all

Accepted... :)

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11094 - Continents

Post by uDebug »

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

http://www.udebug.com/UVa/11094
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 110 (11000-11099)”