11094 - Continents

[SamuraiShaz]

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!

[mrahman]

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

[kason]

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]

no need to use gets.

[JohnsonWang]

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]

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]

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)

[brianfry713]

Input:

Code: Select all

6 6
l---ll
------
------
------
--l---
------
0 0

AC output:
1

[Achilies_Saiful_Buet]

OOOO Allah help me!!!!!!! 10 WA in this problem..plzzzzz help !!thnx brianfry713 for ur suggestion but i'm getting WAAAAAAAAAA again and again!!!!!!!!!!!!!!

[brianfry713]

Don't read from a file.

[Achilies_Saiful_Buet]

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]

Input:

Code: Select all

6 6
----l-
l---l-
l-----
------
--l---
------
4 2

AC output:
2

[Achilies_Saiful_Buet]

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

[eric7237cire]

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]

Code: Select all

removed