11094 - Continents

[SamuraiShaz]

can anybody plz tell me what is the difference between continent and region??? can any region share edge diagonally???

and can the letters be case sensitive???

and what is the answer to the following input case:

Code: Select all

20 20
vqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqVqqqVqqqqqqq
qqqqqqqqqVVVqqqqqqqq
qqqqqqqqqVVVqqqqqqqq
qqqqqqqqqVvVqqqqqqqq
qqqqqqqqVqqqvqqqqqqq
qqqqqqqVqqvqqvqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqvqqqqqqqqq
qqqqqqqqqqvqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
0 0

I ll be very thankful if anybody can help me with answers.
Thank you.

[smile2ka10]

There wont be such testcase, all the input letters are lower case, anyway if we consider all 'V' and 'v' the same character the answer would be: 9 (for the 3*3 square in the middle of the input)

[SamuraiShaz]

it didnt solve the problem. i still get wrong answer!

cud somebody plz expkain to me the following sentence in the problem:

A continent is a set of connected land regions which is completely surrounded by water regions or the end of map. Two regions are assumed to be connected if they have an edge in common.

thanks.

[arsalan_mousavian]

it didnt solve the problem. i still get wrong answer!

cud somebody plz expkain to me the following sentence in the problem:

A continent is a set of connected land regions which is completely surrounded by water regions or the end of map. Two regions are assumed to be connected if they have an edge in common.

thanks.

it is obvious , if you are at cell ( X , Y ) then ( X-1,Y) (X+1,Y) (X,Y-1) (X,Y+1)
are adjacent to it ,and also (X,0) and (X,M-1) are adjacent cells

[SamuraiShaz]

thank you arsalan for your assistance but i already know what you mean!

bcuz i have already solved similar problems like this (for example 572 Oil Deposits) is a same kind of problem which i have solved and it was successfully accepted by online judge. but why is not my solution for 11094 Continents being accepted here i dont understand. my logic is as what you have written that cell (X,Y) is adjacent to (X-1,Y) (X+1,Y) (X,Y-1) (X,Y+1) and also cell (X,0) and (X,M-1) are adjacent cells. but cell (0,Y) and (N-1,Y) are not adjacent. i get it.

i have implemented this in my program but why then do i get wrong answer. i have also calculated the biggest region in which the king is not in. it shows correct output to all the test cases i cud come up with. i m v confused on this one!!!

plz help me out someone.. i m going crazy on this.

[arsalan_mousavian]

did you notice that the input doesn't necessarily consist of 'l' and 'w' ? it can contain any 2 different character ( e.g 'a' and 'b' ) and the character you start from denotes the land
if you have already consider this , you can Post your Code here

[Vexorian]

ok bunch of input:

Code: Select all

1 1
h
0 0

6 6
aaaaaa
bbaaab
aaaabb
abaaba
abbaaa
abbabb
5 5

6 6
aaaaaa
bbaaab
aaaabb
abaaba
abbaba
abbaba
5 4

6 6
abaaab
bbaaab
aaaaab
abaaba
abbaba
abbaba
5 4

6 6
------
------
------
------
------
------
3 3

6 6
--77--
--77--
--77--
--77--
--77--
--77--
2 2

6 6
--77--
------
--77--
--77--
------
--77--
2 2

out put:

Code: Select all

0
6
5
6
0
0
2

[SamuraiShaz]

hello arsalan and vexorian..

first of arsalan u mention that

...the character you start from denotes the land

but shouldnt the Land be where the King currently resides??? i mean the coordinate for the King's current position is Land right?? so his positional letter is land and any other letter is water?? plz correct me if i m wrong!

and thank you vexorian for giving the output but my solution shows exactly what your output shows.

another question i wanted to ask is: is it possible that in judge test cases there will be blank spaces after a row of land and water positions, bcuz i have taken input using getchar() assuming that there is one NEW LINE after each line of input.. i hav solved some string related problems using getchar() before.. so i hope my assumptions are not wrong!

anyway.. i ll post my code after converting it to scanf() function (if i find time). thank you guys for ur suggestions and help.

[arsalan_mousavian]

hello arsalan and vexorian..

first of arsalan u mention that

...the character you start from denotes the land

but shouldnt the Land be where the King currently resides??? i mean the coordinate for the King's current position is Land right?? so his positional letter is land and any other letter is water?? plz correct me if i m wrong!

the king currently resides in (X,Y) that is given in input and the king lives on land , and you should find the bigest Continent which consists of land region except the continent in which the king currently resides

another question i wanted to ask is: is it possible that in judge test cases there will be blank spaces after a row of land and water positions, bcuz i have taken input using getchar() assuming that there is one NEW LINE after each line of input.. i hav solved some string related problems using getchar() before.. so i hope my assumptions are not wrong!

anyway.. i ll post my code after converting it to scanf() function (if i find time). thank you guys for ur suggestions and help.

i have used "cin>> map [j] ;" to read input , it works pretty good , and i am not completely familiar with behaviour of scanf so i am not sure whether it behaves like cin or not

[peace]

Hello everyone, I also got WA in this problem.

I couldn't get the idea how to determine which is land and which is water from the problem's statement.

Could anyone explain it more precisely? thx:)

[SamuraiShaz]

I couldn't get the idea how to determine which is land and which is water from the problem's statement.

Could anyone explain it more precisely? thx:)

I dont know if i m the proper person to be answering this since i got WA myself on this problem. but i did understand the problem well as far as i know.

it is not said in the problem that a certain letter stands for land or water, so any letter can be given for land and water, it may be 0 for land and 1 for water, or a for land and b for water, any arrangment will work as long as there are only 2 letters. it is also not said if they are case-sensitive so small a and capital A may also be used for land and water respectively.

the trick is to luk at the coordinates for the King's current position, since he will be in a continent that he already conquered so King will always be in LAND. so the letter in the position given for King is undisputably LAND for sure, King can never be on water.

so thats how u can determine which letter is for Land and Water since with each testcase, the King's position will be given.

Example:

5 5
ooooo
ooRRo
ooRoo
ooooR
ooRRR
2 2

Here its a sample input where king is at 2, 2 position which is R, so R stands for Land and the other character whatever it is (small letter 'o' here) is Water.

I hope it helps...

I wud request others who has solved it, to correct me if i am wrong since i myself was unable to get it accepted. thank you.

PS: There is a similar problem which is easier than this one in uva acm problemset volume V: 572 Oil Deposits.

[peace]

to SamuraiShaz:

Yes you are right. I got AC after your specific explanation. REALLY Thx for your help!!!

[FAQ]

For someone who still got WA

Code: Select all

4 5
kklkk
klklk
klllk
kkkkk
1 2

output
13

[SamuraiShaz]

guys..... i hav given up.. i may have got over 20 WA in this.. so i m just tired of submitting anymore.. and FAQ ur test case gives me 13 as output.. but i still get WA.. i dont know why.. or whats wrong with my code or logic.. i cant find nothing.. so i m just going to post my whole code so u guys can luk at it and give me some positive analysis on it! thanks in advance!

Code: Select all

#include<stdio.h>

int LandArea, RLIMIT, CLIMIT, kingx, kingy, inRegion;

char W, L;

void KingFound(char LW[][22], int x, int y)
{
	LW[x][y]=W;

	if((y==1) & (LW[x][CLIMIT]==L))
		KingFound(LW,x,CLIMIT);

	if((y==CLIMIT) & (LW[x][1]==L))
		KingFound(LW,x,1);
	
	if(LW[x-1][y]==L)
		KingFound(LW,x-1,y);

	if(LW[x][y+1]==L)
		KingFound(LW,x,y+1);
	
	if(LW[x+1][y]==L)
		KingFound(LW,x+1,y);

	if(LW[x][y-1]==L)
		KingFound(LW,x,y-1);

}

void LandFound(char LW[][22], int x, int y)
{
	if((x==kingx) & (y==kingy)) {
		LandArea=0;
		KingFound(LW,x,y);
	}

	LW[x][y]=W;

	if((y==1) & (LW[x][CLIMIT]==L)) {
		LandArea++;
		LandFound(LW,x,CLIMIT);
	}

	if((y==CLIMIT) & (LW[x][1]==L)) {
		LandArea++;
		LandFound(LW,x,1);
	}


	if(LW[x-1][y]==L) {
		LandArea++;
		LandFound(LW,x-1,y);
	}

	if(LW[x][y+1]==L) {
		LandArea++;
		LandFound(LW,x,y+1);
	}

	if(LW[x+1][y]==L) {
		LandArea++;
		LandFound(LW,x+1,y);
	}

	if(LW[x][y-1]==L) {
		LandArea++;
		LandFound(LW,x,y-1);
	}

}

void main()
{
	//freopen("11094.txt","r",stdin);

	int i, j, row, col;
	char LandWater[22][22];
	while(scanf("%d %d\n", &row, &col)==2) {
		RLIMIT = row;
		CLIMIT = col;
		inRegion=0;

		LandArea=0;

		for(i=1;i<=row;i++) {
			for(j=1;j<=col;j++) {
				LandWater[i][j]=getchar();
			}
			getchar();
		}
		
		scanf("%d %d", &kingx, &kingy);
		kingx=kingx + 1;
		kingy=kingy + 1;
		
		L = LandWater[kingx][kingy];
		
		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;
		}


		for(j=0;j<=col+1;j++) {
			LandWater[0][j]=W;
			LandWater[row+1][j]=W;
		}

		for(i=0;i<=row+1;i++) {
			LandWater[i][0]=W;
			LandWater[i][col+1]=W;
		}

		int max_LandArea = 0;

		for(i=1;i<=row;i++) {
			for(j=1;j<=col;j++) {
				if(LandWater[i][j]==L) {
					LandArea=1;
					LandFound(LandWater,i,j);
					if(LandArea>max_LandArea)
						max_LandArea=LandArea;
					inRegion++;
				}
			}
		}
		//printf("Region:%d Land:%c Water:%c CanConquer:%d\n", inRegion, L, W, max_LandArea);
		printf("%d\n", max_LandArea);
	}
	//fclose(stdin);
}

and here is the testcases input file i hav tested my code with:

11094.txt:

4 5
kklkk
klklk
klllk
kkkkk
1 2

1 1
h
0 0

6 6
aaaaaa
bbaaab
aaaabb
abaaba
abbaaa
abbabb
5 5

6 6
aaaaaa
bbaaab
aaaabb
abaaba
abbaba
abbaba
5 4

6 6
abaaab
bbaaab
aaaaab
abaaba
abbaba
abbaba
5 4

6 6
------
------
------
------
------
------
3 3

6 6
--77--
--77--
--77--
--77--
--77--
--77--
2 2

6 6
--77--
------
--77--
--77--
------
--77--
2 2

20 20
qvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvv
qqqqqqqqqqqqqqqqqqqq
vvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvv
qqqqqqqqqqqqqqqqqqqq
vvvvvvvvqvvvvvvvvvvv
vvvvvvvvqvvvvvvvvvvv
vvvvvvvvqVvVvvvvvvvv
vvvvvvvvqvvvvvvvvvvv
vvvvvvvVqvvvvvvvvvvv
qqqqqqqqqqqqqqqqqqqq
vvvvvvvvvvvvvvvvvvvq
vvvvvvvvvvvvvvvvvvvq
vvvvvvvvvvvvvvvvvvvq
vvvvvvvvvvvvvvvvvvvq
0 0

1 1
q
0 0

1 1
w
0 1

2 2
w@
@@
0 0

2 2
w@
@@
0 1

2 2
w@
@w
0 0

20 20
~qqqqqqqqqqqqqqqqqq~
qqqqqqqqqqqqqqqqqqqq
~qqqqqqqqqqqqqqqqqq~
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
~qqqqqqqqqqqqqqqqqq~
2 0

20 20
@@qqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqq@qqq@qqqqqqq
qqqqqqqqq@@@qqqqqqqq
qqqqqqqqq@@@qqqqqqqq
qqqqqqqqq@@@qqqqqqqq
qqqqqqqq@qqq@qqqqqqq
@qqqqqq@qq@qq@qqqqq@
qqqqqqqqqqqqqqqqqqq@
qqqqqqqqqq@qqqqqqqqq
qqqqqqqqqq@qqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
@@qqqqqqqqqqqqqqqqqq
10 10

20 20
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqVVVVVVVVVV
qqqqqqqqqqVVVVVVVVVq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqVqqqqqqqqq
qqqqqqqqqqVqqqqqqqqq
qqqqqqqqqqVqqqqqqqqq
qqqqqqqqqqVqqqqqqqqq
VqqqqqqqqqVVVVVVVVVV
qqqqqqqqqqVqqqqqqqqq
VVVVVVqqqqVqqqqqqqqq
vvvqqqqqqqqqqqqvVVVV
qvvVqqqqqqqqqqqqqqqq
vVVqqqqqqqqqqqVVVVVq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqq
10 10

5 5
wwwww
wwllw
wwwww
wllww
wwwww
1 3

5 5
lwwww
wllww
lwlll
wwwlw
wllww
2 2

7 5
wwwww
w@@@w
wwwww
wwwww
ww@@@
@www@
wwww@
5 0

5 5
ooooo
ooiii
iiiii
oiioo
ooooo
3 3

6 6
wwllww
llllww
wwwwww
llwlll
llwlll
wwwwww
0 1

6 6
wzzzww
wwwzww
wwzzww
zwwwwz
wwwwww
wwwwzz
2 3

6 6
wwMwww
wwwwww
wwwwMw
MwwwwM
wwwwww
wwwMww
5 3

here is the output:

13
0
6
5
6
0
0
2
49
0
0
0
0
1
2
3
19
2
2
3
7
0
2
2

[Vexorian]

this input will fail in your program (correct result are 2 zeros)

Code: Select all

3 3
---
-#-
---
1 1

3 3
---
---
---
0 0

You only need to know the land character, after that whenever you want to recognize water simply ask if it is different than the land character