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

SamuraiShaz
New poster
Posts: 9
Joined: Mon Feb 21, 2005 10:42 am
Location: Dhaka

Post by SamuraiShaz » Tue Sep 26, 2006 10:41 am

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
Location: Bangladesh
Contact:

Post by mrahman » Tue Oct 10, 2006 1:23 pm

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

Post by kason » Mon Mar 24, 2008 8:55 pm

for who still WA

here's some advise


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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11094 - Continents

Post by Shafaet_du » Thu Jun 23, 2011 3:13 pm

no need to use gets.

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

Re: 11094 - Continents

Post by JohnsonWang » Sat Jul 09, 2011 11:54 am

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];

			if( adjacent_column == world_map[0].size() ) adjacent_column = 0;
			if( adjacent_column == -1 ) adjacent_column = world_map[0].size() - 1;

			if( is_in_range( adjacent_row, adjacent_column, world_map.size(), world_map[0].size() ) && world_map[adjacent_row][adjacent_column] == land )
			{
				world_map[adjacent_row][adjacent_column] = 'w';
				stk.push( make_pair( adjacent_row, adjacent_column ) );
				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

Post by lucastan » Thu Aug 18, 2011 5:24 am

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
Location: Dhaka,Bangladesh

Re: 11094 - Continents

Post by Achilies_Saiful_Buet » Mon Apr 02, 2012 6:10 am

Plz helpppp!!!!
can some one tell me what's wrong with my code????
i'm getting coninuous WA!!!!!!!! :x :x 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

Post by brianfry713 » Tue Apr 03, 2012 12:08 am

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
Location: Dhaka,Bangladesh

Re: 11094 - Continents

Post by Achilies_Saiful_Buet » Fri Apr 06, 2012 7:06 pm

OOOO Allah help me!!!!!!! 10 WA in this problem..plzzzzz help !!thnx brianfry713 for ur suggestion but i'm getting WAAAAAAAAAA again and again!!!!!!!!!!!!!! :x :x :x :x :x :x
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

Post by brianfry713 » Sat Apr 07, 2012 1:11 am

Don't read from a file.
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
Location: Dhaka,Bangladesh

Re: 11094 - Continents

Post by Achilies_Saiful_Buet » Sat Apr 07, 2012 7:28 am

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

Post by brianfry713 » Mon Apr 09, 2012 10:28 pm

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
Location: Dhaka,Bangladesh

Re: 11094 - Continents

Post by Achilies_Saiful_Buet » Wed Apr 11, 2012 12:43 pm

thnx brianfry713 a lot :) i got accepted.. :D 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

Post by eric7237cire » Sun Mar 31, 2013 1:43 am

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

Post by faraa_T » Sun Jul 28, 2013 11:58 pm

Code: Select all

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

Post Reply

Return to “Volume 110 (11000-11099)”