722 - Lakes

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

722 - Lakes

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? :roll:

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

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

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

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.

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

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

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

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.

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

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

12

1

1

3

6

5

6

1

7

78

25
What's wrong with my code? :cry:

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

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 :wink:

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

Post by Roby » Wed Nov 23, 2005 5:13 am

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

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
New poster
Posts: 1
Joined: Sat Oct 11, 2008 11:56 am

Re: 722 - Lakes

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

      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

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.

Post Reply

Return to “Volume 7 (700-799)”