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

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

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

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;
char s;

int sum;

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))]++;
}

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

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

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;
bool Visit;

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

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???

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

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

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 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???

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

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... :(

Code: Select all

Accepted... :)

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

Re: 11094 - Continents

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!