## 722 - Lakes

Moderator: Board moderators

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

### 722 - Lakes

Hmm... this problem looks like problem 469 in Volume IV. Is it true? If it is true, the solution wouldn't be much different with 469 solution then, isn't it?

Can someone clarify this? Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
Hey, this problems seems easy but the truth is different...
I've coded and here's my code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 105

typedef struct queue queue;

struct queue
{
int x, y;
queue * next;
} * head, * curr, * tail;

char map[MAX][MAX];

void createQueue( void )
{
head = curr = tail = NULL;
}

void enqueue( const int x, const int y )
{
curr = ( queue * ) malloc ( sizeof( queue ) );
curr->x = x;
curr->y = y;

if ( head == NULL )
else
{
tail->next = curr;
tail = curr;
}

tail->next = NULL;
}

void dequeue( int & x, int & y )
{
if ( head != NULL )
{

free( curr );
}
}

int floodFill( int x, int y, const int rows, const int cols )
{
int i = 0, counter = 0;
int ax = { -1, -1, 0, 1, 1, 1, 0, -1 };
int ay = { 0, 1, 1, 1, 0, -1, -1, -1 };

if ( map[x][y] == '0' )
{
createQueue();
enqueue( x, y );
map[x][y] = '1';
}

while ( head != NULL )
{
dequeue( x, y );
counter++;

// search from north till north west
for ( i = 0; i < 8; i++ )
if ( x + ax[i] >= 0 && x + ax[i] < rows &&
y + ay[i] >= 0 && y + ay[i] < cols &&
map[ x + ax[i] ][ y + ay[i] ] == '0' )
{
enqueue( x + ax[i], y + ay[i] );
map[ x + ax[i] ][ y + ay[i] ] = '1';
}
}

return counter;
}

void printMap( int m, int n )
{
int i = 0, j = 0;

for ( i = 0; i < m; i++ )
{
for ( j = 0; j < n; j++ )
putchar( map[i][j] );
putchar(' \n' );
}
putchar(' \n' );
}

int main()
{
int cases = 0, x = 0, y = 0, i = 0, k = 0, rows = 0, cols = 0;
char input = 0, dummy = 0;

scanf( "%d\n", &cases );

for ( k = 0; k < cases; k++ )
{
if ( k )
printf( "        \n" );

memset( map, '\0', sizeof( map ) );
gets( map );

for ( i = 0, x = 0; map[i] == ' '; i++ );

while ( map[i] != ' ' )
{
x *= 10;
x += ( map[i] - 48 );
i++;
}

while ( map[i] == ' ' ) i++;
y = 0;

while ( map[i] != '\0' )
{
y *= 10;
y += ( map[i] - 48 );
i++;
}

memset( map, '1', sizeof( map ) );
memset( map, '1', sizeof( map ) );
rows = 1; cols = 1;

while ( scanf( "%c", &input ) == 1 )
{
if ( input == '\n' )
{
if ( dummy == ' ' )
break;
else
{
rows++; i = cols; cols = 1;
memset( map[rows], '1', sizeof( map[rows] ) );
}
}
else if ( input != ' ' )
map[rows][cols++] = input;

dummy = input;
}

rows++;
cols = strlen( map );

//printMap( rows, i );

printf( "        %d\n", floodFill( x, y, rows, i + 1 ) );
}

return 0;
}``````
can someone look up to my code and find the mistake? I've tested with input below:

Code: Select all

``````        3

02 01
1001101
0011111
0001001
1100011
1111111
1100110
1110111

01 01
1001101
0011111
0001001
1100011
1111111
1100110
1110111

06 07
1001101
0011111
0001001
1100011
1111111
1100110
1110111

``````
And below is my program output:

Code: Select all

``````        12

0

1
``````
BTW, I got Runtime Error for this problem. Please help me... mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
This problem is actually easy. It's same as 469.
You may have confusion in the input/output. Actally there is no leading/trailing spaces in input and output.
Hope it helps.

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
Thanx for the reply, mamun... now, I got WA.
I've revised my code and tested with the input below:

Code: Select all

``````4

02 01
1001101
0011111
0001001
1100011
1111111
1100110
1110111

01 01
1001101
0011111
0001001
1100011
1111111
1100110
1110111

09 09
1001101
0011111
0001001
1100011
1111111
1100110
1110111

06 07
1001101
0011111
0001001
1100011
1111111
1100110
1110111
``````
My program gave output like this:

Code: Select all

``````12

0

0

1
``````
Is it correct? I just confused about the coordinate given for example:

Code: Select all

``````01 01
1001101
0011111
0001001
1100011
1111111
1100110
1110111``````
Is it mean row 1 and column 1 of this array (interpreted one):

Code: Select all

``````rc| 012345678
--+-----------
0 | 111111111
1 | 110011011
2 | 100111111
3 | 100010011
4 | 111000111
5 | 111111111
6 | 111001101
7 | 111101111
8 | 111111111

r = row, c = column``````
or it should be row 0 and column 0? And what about coordinate 07 07? What should it be?
Please help me ... and thanx for advance

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
The index of the map is as described in the problem. The first row in the input is indexed 1 and the first column indexed 1. Similarly the last coordinate is (m,n) where m = number of row and n = number of column. So the 0th and (m+1)th row and 0th and (n+1)th column are the boundary filled with 1 which you have to do manually.
We are interested in finding the area of a region of horizontally or vertically connected "water" cells totally enclosed by a boundary of "land" cells, given the location of a "water" cell in the region.
Now you can see why you get wrong answer. The answer can be never 0. Your second and third sample input is wrong.

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
But still getting WA... I've changed my input to below:

Code: Select all

``````11

02 01
1001101
0011111
0001001
1100011
1111111
1100110
1110111

01 06
1001101
0011111
0001001
1100011
1111111
1100110
1110111

06 07
1001101
0011111
0001001
1100011
1111111
1100110
1110111

06 04
1001101
0011111
0001001
1100011
1111111
1100110
1110111

06 07
100110111
001111111
000100111
110001101
111111110
110011001
111011110
110011101

06 03
100110111
001111111
000100111
110001101
111111110
110011001
111011110
110011101

04 08
100110111
001111111
000100111
110001101
111111110
110011001
111011110
110011101

02 02
111
101
111

02 03
10101
01010
10101

05 06
101010101010
010101010101
101010101010
010101010101
101010101010
010101010101
101010101010
010101010101
101010101010
010101010101
101010101010
010101010101
101010101010

05 05
00000
00000
00000
00000
00000
``````
And here's my output:

Code: Select all

``````12

1

1

3

6

5

6

1

7

78

25
``````
What's wrong with my code? mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
You did everything correct but just missed out a line.
We are interested in finding the area of a region of horizontally or vertically connected "water" cells totally enclosed by a boundary of "land" cells
So you need to travel in 4 directions only. Don't travel diagonally. Your output for your sample should be
• 12

1

1

3

2

5

1

1

1

1

25
Congratulations! Now you should be done Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
THANK YOU VERY MUCH, MAMUN...
Finally I got AC with 0.2xx seconds...

nardhar
New poster
Posts: 4
Joined: Wed Oct 10, 2007 6:09 pm
plz somebody help!, i get RTE with java, guess its something with the ReadLn function, because it doesn't return null when there is a blank line

here is the code

Code: Select all

``````class Main
{
static int mat[][];
static int c;
{
byte linea[] = new byte [max];
int largo = 0, car = -1;
try{
while (largo < max){
if ((car < 0) || (car == '\n')) break;
linea [largo++] += car;
}
}
catch (IOException e){
return (null);
}
if ((car < 0) && (largo == 0)) return (null);  // eof -->appears not to return eof
return (new String (linea, 0, largo));
}
public static void main (String args[])
{
Main myWork = new Main();
myWork.Begin();
}
void Begin()
{
String input;
StringTokenizer idata;
String fila;
int casos,nrofila,x,y;
mat=new int;
idata = new StringTokenizer (input);
casos=Integer.parseInt(idata.nextToken());
while (casos>0){
for (int i=0;i<=101;i++)
for (int j=0;j<=101;j++)
mat[i][j]=1;
nrofila=0;
c=0;
idata = new StringTokenizer (input);
x=Integer.parseInt(idata.nextToken());
y=Integer.parseInt(idata.nextToken());
while ((input=Main.ReadLn(255))!=null){//mientras haya datos los lee y los copia a la matriz
nrofila++;
if (input.length()<=1) break;
idata = new StringTokenizer (input);
fila=idata.nextToken();
for (int j=1;j<=fila.length();j++){
mat[nrofila][j]=fila.charAt(j-1)-48;
}
}
cuenta(x,y);
//imprime el numero
System.out.println(c);
casos--;
}
}
public void cuenta(int x,int y){
if (mat[x][y]==2){
}else if(mat[x][y]==1){
//es tierra
}else if(mat[x][y]==0){
//es agua
c++;
mat[x][y]=2;//lo visita
cuenta(x-1,y);
cuenta(x+1,y);
cuenta(x,y-1);
cuenta(x,y+1);
}
}
}``````

t.jerabek
New poster
Posts: 1
Joined: Sat Oct 11, 2008 11:56 am

### Re: 722 - Lakes

I need help pleas.
This is my code:

Code: Select all

``````import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {

private int[][] field;
private int[][] moves = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
private int moveCount = 4;
private static int MAX_SIZE = 101;
private ArrayList<int[]> queue;
private int waterCount;

public static void main(String[] args) throws IOException {

Main m = new Main();
System.in));
line = line.trim();
int count = Integer.parseInt(line);
for (int i = 0; i < count; i++) {
m.fillField();

line = line.trim();

int sX = Integer.parseInt(line.substring(0, 2));
int sY = Integer.parseInt(line.substring(3, 5));

m.setStart(sX, sY);
line = null;
int c = 0;
c++;
line = line.trim();
if(line.length()<=0 || line.length()>MAX_SIZE-2){
break;
}
for (int j=0;j<line.length();j++){
if (line.charAt(j)=='0'){
}
if (line.charAt(j)=='1'){
}
}
}
m.markField();
//m.showField();

m.printWaterCount();

}
}

public void addToField(int x, int y, int value){
field[x][y] = value;
}
public void printWaterCount() {
if (waterCount>0){
System.out.println("        "+waterCount);
System.out.println("        ");
}
}
public void setStart(int x, int y){
}
public void fillField() {
waterCount = 0;
queue = new ArrayList<int[]>();
field = new int[MAX_SIZE][MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
field[i][j] = 2;
}
}
}
/*
public void showField() {
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
if (field[i][j]!=2){
System.out.print(field[i][j]);
}
}
System.out.println("");
}
}
*/
public void markField() {
while (queue.size() > 0) {
int[] item = removeFormQueue();
int x = item;
int y = item;
if (field[x][y] == 0) {
waterCount++;
field[x][y] = 3;
for (int i = 0; i < moveCount; i++) {
int mX = x + moves[i];
int mY = y + moves[i];
if (field[mX][mY] == 0) {
}
}
}
}
}

public void addToQueue(int x, int y) {
int[] p = { x, y };
}

public int[] removeFormQueue() {
int[] head = queue.get(queue.size() - 1);
queue.remove(queue.size() - 1);
}
}

``````
but still WA.
My output for test data:

Code: Select all

``````      12

1

1

3

2

5

1

1

1

1

25
``````

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

### Re: 722 - Lakes

Be careful on input parsing for this one - THERE IS NO BLANK LINE AFTER THE LAST CASE.
You just get an eof.