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 » Mon Jul 29, 2013 8:07 am

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 » Mon Jul 29, 2013 1:04 pm

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 » Wed Aug 21, 2013 1:57 pm

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 » Wed Aug 21, 2013 10:04 pm

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 » Wed Oct 08, 2014 5:55 am

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 » Wed Oct 08, 2014 9:14 pm

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 » Mon Feb 02, 2015 9:42 am

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 » Tue Feb 03, 2015 12:04 am

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 » Tue Feb 03, 2015 6:55 am

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 » Wed Feb 04, 2015 1:11 am

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 » Wed Feb 04, 2015 5:21 am

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 » Wed Feb 04, 2015 9:35 pm

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 » Sun Mar 01, 2015 7:41 pm

Code: Select all

Accepted... :)

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

Re: 11094 - Continents

Post by uDebug » Tue Apr 07, 2015 12:12 pm

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)”