722 - Lakes

Roby · Post by **Roby** » Sat Nov 19, 2005 9:25 am

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 · Post by **Roby** » Mon Nov 21, 2005 7:34 am

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 )
    head = tail = curr;
 else
 {
    tail->next = curr;
    tail = curr;
 }

 tail->next = NULL;
}

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

    curr = head;
    head = head->next;
    free( curr );
 }
}

int floodFill( int x, int y, const int rows, const int cols )
{
 int i = 0, counter = 0;
 int ax[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
 int ay[8] = { 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], '\0', sizeof( map[0] ) );
    gets( map[0] );

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

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

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

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

    memset( map[0], '1', sizeof( map[0] ) );
    memset( map[1], '1', sizeof( map[1] ) );
    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[0] );

    //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

And below is my program output:

Code: Select all

BTW, I got Runtime Error for this problem. Please help me...

mamun · Post by **mamun** » Mon Nov 21, 2005 11:08 pm

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 · Post by **Roby** » Tue Nov 22, 2005 5:57 am

Thanx for the reply, mamun... now, I got WA.
I've revised my code and tested with the input below:

Code: Select all

My program gave output like this:

Code: Select all

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

Code: Select all

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 · Post by **mamun** » Tue Nov 22, 2005 1:07 pm

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 · Post by **Roby** » Tue Nov 22, 2005 6:15 pm

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

What's wrong with my code?

mamun · Post by **mamun** » Tue Nov 22, 2005 11:11 pm

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 · Post by **Roby** » Wed Nov 23, 2005 5:13 am

THANK YOU VERY MUCH, MAMUN...
Finally I got AC with 0.2xx seconds...

nardhar · Post by **nardhar** » Wed Oct 17, 2007 2:59 am

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;
   static String ReadLn (int max)
    {
        byte linea[] = new byte [max];
        int largo = 0, car = -1;
        try{
            while (largo < max){
                car = System.in.read();
                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[102][102];
      input=Main.ReadLn (255);
      idata = new StringTokenizer (input);
      casos=Integer.parseInt(idata.nextToken());
      input=Main.ReadLn (255);//lee un enter
      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;
         input=Main.ReadLn (255);//lee coordenadas
         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 la cantidad de agua
         cuenta(x,y);
         //imprime el numero
         System.out.println(c);
         casos--;
      }
    }
    public void cuenta(int x,int y){
       if (mat[x][y]==2){
          //ya ha sido visitado
       }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);
       }
    }
}

thks in advance

t.jerabek · Post by **t.jerabek** » Sat Oct 11, 2008 12:00 pm

I need help pleas.
This is my code:

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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();
			BufferedReader reader = new BufferedReader(new InputStreamReader(
					System.in));
			String line = reader.readLine();
			line = line.trim();
			int count = Integer.parseInt(line);
			reader.readLine();
			for (int i = 0; i < count; i++) {
				m.fillField();
				
				line = reader.readLine();
				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;
				while ((line = reader.readLine()) != null) {
					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'){
							m.addToField(c, j+1, 0);
						}
						if (line.charAt(j)=='1'){
							m.addToField(c, j+1, 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){
		addToQueue(x, 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[0];
			int y = item[1];
			if (field[x][y] == 0) {
				waterCount++;
				field[x][y] = 3;
				for (int i = 0; i < moveCount; i++) {
					int mX = x + moves[i][0];
					int mY = y + moves[i][1];
					if (field[mX][mY] == 0) {
						addToQueue(mX, mY);
					}
				}
			}
		}
	}

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

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

but still WA.
My output for test data:

Code: Select all

anacharsis · Post by **anacharsis** » Tue Nov 03, 2015 5:16 pm

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

OJ Board

722 - Lakes

722 - Lakes

Re: 722 - Lakes

Re: 722 - Lakes