## 11094 - Continents

Moderator: Board moderators

SamuraiShaz
New poster
Posts: 9
Joined: Mon Feb 21, 2005 10:42 am
Location: Dhaka
vex u r right! there was in fact a problem there...

but i m going crazy.. cuz i still get WA!

i fixed my code.

i replaced only the portion which was looking for Water letter in the array:

Code: Select all

``````	int temp=0;
for(i=1;i<=row;i++) {
for(j=1;j<=col;j++) {
if(LandWater[i][j]!=L) {
W = LandWater[i][j];
temp=1;
break;
}
}
if(temp)
break;
}
``````
with the following piece of code, where Water is assigned as following:

Code: Select all

``````	if(L>100)
W = L-1;
else
W = L+1;
``````
i compared to 100 since if the letter for Land is 127 than (L+1) would have problems, so i took caution.

and this code gives correct output for all the testcases including yours. but i got WA.. i m going to be MAD with this.. i nvr in my life got so many WA as with this problem!
- Shaz

Sharing a bit of knowledge takes you one step closer to immortality!

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Contact:
Dear SamuraiShaz, Why you do this

Code: Select all

``````if(L>100)
W = L-1;
else
W = L+1;``````
You don't have to determine water denoted character. If you really want to do so use digit in place of Letter. Becasue in problem statement

Maps are given as M x N tables, filled with at most two different letters denoting land and water regions

try to take input using scanf() function.

Sorry for my poor english
Practice Makes a man perfect

kason
New poster
Posts: 4
Joined: Sat Dec 01, 2007 12:44 pm
for who still WA

the problem only say:

"Region with coordinates (x,N-1) should be assumed to have a common edge with region (x,0) for every x between 0 and M-1 (inclusive)"

so (M-1,y) and (0,y) dont have the same edge!!!

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 11094 - Continents

no need to use gets.

JohnsonWang
New poster
Posts: 4
Joined: Wed May 11, 2011 6:14 am

### Re: 11094 - Continents

Hi,

I keep getting a TLE on this problem. I have checked my I/O against all the sets provided during this thread, and they match up...please let me know if you see something blatantly wrong.

Thanks!

Code: Select all

``````#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int row_direction[] = { 1, -1, 0, 0 };
int column_direction[] = { 0, 0, 1, -1 };

bool is_in_range( int row, int column, int num_rows, int num_columns )
{
if( row >= 0 && column >= 0 && row < num_rows && column < num_columns ) return true;
return false;
}

int find_continent_area( int row, int column, vector < vector <char> >& world_map, char land )
{
int num_nodes = 1;
world_map[row][column] = 'w';

stack < pair <int, int> > stk;
stk.push( make_pair( row, column ) );

while( !stk.empty() )
{
pair <int, int> cur = stk.top();
stk.pop();

for( int i = 0; i < 4; i++ )
{
int adjacent_row = cur.first + row_direction[i];
int adjacent_column = cur.second + column_direction[i];

{
num_nodes++;
}
}
}

return num_nodes;
}

int main()
{
int num_rows, num_columns;
while( cin >> num_rows >> num_columns )
{
vector <char> g_tmp( num_columns, 0 );
vector < vector <char> > world_map( num_rows, g_tmp );

for( int row = 0; row < num_rows; row++ )
for( int column = 0; column < num_columns; column++ )
cin >> world_map[row][column];

int starting_row, starting_column;
cin >> starting_row >> starting_column;

char land = world_map[starting_row][starting_column];

for( int row = 0; row < num_rows; row++ )
for( int column = 0; column < num_columns; column++ )
if( world_map[row][column] != land )
world_map[row][column] = 'w';

find_continent_area( starting_row, starting_column, world_map, land );

int maximum_continent_area = 0;
for( int row = 0; row < num_rows; row++ )
for( int column = 0; column < num_columns; column++ )
if( world_map[row][column] == land )
maximum_continent_area = max( maximum_continent_area, find_continent_area( row, column, world_map, land ) );

cout << maximum_continent_area << endl;
}

return 0;
}``````

lucastan
New poster
Posts: 10
Joined: Sat Jul 02, 2011 6:46 am

### Re: 11094 - Continents

Gotchas:
- M is the # of rows! N is # of columns
'x' refers to the row index!

- Can be any chars other than l and w

- The grid wraps around at column 0 and column N-1

- Only up, down, left and right are considered adjacent

- Look for largest land area except the initial one the King's on

Simple flood fill suffices

Hope it helps!

This is a good example of an easy yet tricky and lame problem

Achilies_Saiful_Buet
New poster
Posts: 16
Joined: Wed Mar 28, 2012 7:24 pm

### Re: 11094 - Continents

Plz helpppp!!!!
can some one tell me what's wrong with my code????
i'm getting coninuous WA!!!!!!!! here is my code-(FYI i've checked all the test cases posted here)
Last edited by Achilies_Saiful_Buet on Wed Apr 11, 2012 12:40 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

Input:

Code: Select all

``````6 6
l---ll
------
------
------
--l---
------
0 0``````
AC output:
1
Check input and AC output for thousands of problems on uDebug!

Achilies_Saiful_Buet
New poster
Posts: 16
Joined: Wed Mar 28, 2012 7:24 pm

### Re: 11094 - Continents

OOOO Allah help me!!!!!!! 10 WA in this problem..plzzzzz help !!thnx brianfry713 for ur suggestion but i'm getting WAAAAAAAAAA again and again!!!!!!!!!!!!!!
Last edited by Achilies_Saiful_Buet on Wed Apr 11, 2012 12:39 pm, edited 2 times in total.

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

### Re: 11094 - Continents

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

Achilies_Saiful_Buet
New poster
Posts: 16
Joined: Wed Mar 28, 2012 7:24 pm

### Re: 11094 - Continents

bryianfry713 boss i'mnot reading from a file .that particular line was to test test cases.i forgot to give the slashes here but i'm getting WA without it. plzzzz check my bug.plzzzzzzzzzzzzzzz!!

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

### Re: 11094 - Continents

Input:

Code: Select all

``````6 6
----l-
l---l-
l-----
------
--l---
------
4 2``````
AC output:
2
Check input and AC output for thousands of problems on uDebug!

Achilies_Saiful_Buet
New poster
Posts: 16
Joined: Wed Mar 28, 2012 7:24 pm

### Re: 11094 - Continents

thnx brianfry713 a lot i got accepted.. actually i misunderstood the wrapping thing in this problem

eric7237cire
New poster
Posts: 4
Joined: Sat Mar 30, 2013 4:06 pm

### Re: 11094 - Continents

Wow.

Ok, so in case anyone makes the same silly mistake I did.

There is only a blank line between INPUT cases. Not output.

Each output is just on one line.

I found that out after I made it work for arbitrary whitespace characters as input, ie grids like

4 4
a
aa
aaa
aaaa
3 3

which is totally not necessary. You can assume the characters used are not '\t' ' ' or '\n'

*facepalm*

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

### Re: 11094 - Continents

Code: Select all

``removed``
Last edited by faraa_T on Mon Jul 29, 2013 1:01 pm, edited 1 time in total.