Algoritmo de llenado de inundaciones en Java -- java campo con algorithm camp codereview Relacionados El problema

Flood fill algorithm in Java


5
vote

problema

Español

Haciendo la tarea, implementación de los rellenos de inundación del algoritmo. Estoy escribiendo un programa a esta guía: http://en.wikipedia.org/wiki/flood_fill. Y tengo algunas preguntas:

  1. ¿Es normal especificar los parámetros en la función reemplaza el color de cualquier carácter bucketFill.fill (0, 0, '*', 'O'); , no sé qué tipo de color será inicialmente a estas coordenadas?
  2. ¿Un algoritmo es correcto? Lo escribí, por ejemplo, en Wikipedia, pero el resultado de mi programa es el siguiente:

      buttons[3]0  

    Creo que debe ser esto:

      buttons[3]1  

Mi código:

  buttons[3]2  
Original en ingles

Doing homework, implementation of the algorithm flood fills. I'm writing a program to this guide: http://en.wikipedia.org/wiki/Flood_fill. And I have some questions:

  1. Is it normal to specify the parameters in function replaces the color of any character bucketFill.fill (0, 0, '*', 'O');, I do not know what kind of color will be initially to these coordinates?
  2. An algorithm is correct? I wrote it for example in Wikipedia, but the result of my program is as follows:

    @@@@@ @@@@@ @@@@@ @@@@@ @@@@@ @@@@@ @@@@@ 

    I think must be this:

    *@@@@ @@@@@ @@#@@ @@@@@ @@@@@ @@@## @@@@@ 

My code:

class BucketFill {      private char[][] pixels;      public BucketFill(char[][] pixels) {         this.pixels = pixels;     }      public void fill(int x, int y, char newColor, char oldColor) {         if (x < 0) return;         if (y < 0) return;         if (x >= pixels.length) return;         if (y >= pixels[x].length) return;          oldColor = pixels[x][y];          if (newColor == pixels[x][y]) return;         if (oldColor != pixels[x][y]) return;          pixels[x][y] = newColor;          fill(x - 1, y, newColor, oldColor);         fill(x + 1, y, newColor, oldColor);         fill(x, y - 1, newColor, oldColor);         fill(x, y + 1, newColor, oldColor);     }      public void inspect() {         for (int y = 0; y < pixels.length; y++) {             for (int x = 0; x < pixels[y].length; x++) {                 System.out.print(pixels[y][x]);             }             System.out.print("\n");         }     }      public static void main(String argv[]) {         char pixels[][] =         {             { 'O', 'X', 'X', 'X', 'X' },             { 'X', 'O', 'O', 'O', 'X' },             { 'X', 'O', '#', 'O', 'X' },             { 'X', 'O', 'O', 'O', 'X' },             { 'X', 'X', 'X', 'X', 'X' },             { 'X', 'X', 'X', '#', '#' },             { 'X', 'X', 'X', 'X', 'X' }         };         BucketFill bucketFill = new BucketFill(pixels);         bucketFill.fill(0, 0, '*', 'O');         bucketFill.fill(3, 0, 'O', 'O');         bucketFill.fill(2, 1, '@', 'O');         bucketFill.inspect();     } } 
     

Lista de respuestas

5
 
vote
vote
La mejor respuesta
 
  1. Normalmente, no hay necesidad de especificar el color para cambiar. Solo necesita especificar las coordenadas y dejarlo en la rutina de llenado de inundación para averiguar qué color está en esa ubicación. Definiría otro método que sea público, y haga que el método recursivo sea un método de implementación privada. El método público buscaría el color en la ubicación y luego llamaría al método privado.

      public void fill(int x, int y, char newColor) {     fill(x, y, newColor, pixels[x][y]); }  private void fill(int x, int y, char newColor, char oldColor) {     ... }   
  2. No está usando oldColor correctamente; Estás sobrescribiendo el valor del parámetro. La línea:

      oldColor = pixels[x][y];   

    debe ser eliminado o (mejor) enmendado a:

      char color = pixels[x][y];   

    y las líneas:

      if (newColor == pixels[x][y]) return; if (oldColor != pixels[x][y]) return;   

    debe cambiarse para usar el const0 Variable:

      const1  

    Aparte de eso, ha implementado el algoritmo correctamente.

    Vale la pena señalar que la forma en que este algoritmo usa la recursión podría llevar a un desbordamiento de pila para un bloque de color grande. Además, por DINT de los +1 y -1, terminará llenando las llamadas () varias veces para cada celda.

 
  1. Normally there's no need to specify the color to change from. You only need to specify the coordinates and leave it up to the flood fill routine to find out what color is at that location. I would define another method that is public, and make the recursive method a private implementation method. The public method would look up the color at the location and then call the private method.

    public void fill(int x, int y, char newColor) {     fill(x, y, newColor, pixels[x][y]); }  private void fill(int x, int y, char newColor, char oldColor) {     ... } 
  2. You are not using oldColor correctly; you're overwriting the parameter value. The line:

    oldColor = pixels[x][y]; 

    should either be deleted or (better) amended to:

    char color = pixels[x][y]; 

    And the lines:

    if (newColor == pixels[x][y]) return; if (oldColor != pixels[x][y]) return; 

    should then be changed to use the color variable:

    if (newColor == color) return; if (oldColor != color) return; 

    Other than that, you have implemented the algorithm correctly.

    It's worth noting that the way this algorithm uses recursion could lead to a stack overflow for a large block of color. Also, by dint of the +1 and -1, will end up calling fill() multiple times for each cell.

 
 

Relacionados problema

5  Orden de número más grande en cadena  ( Largest number order in string ) 
Dada una cadena, suponiendo que la cadena sea solo números, reorganice la cadena a la que sea el mayor número posible. a continuación es mi solución al pr...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

1  Compruebe si dos cadenas son permutación entre sí  ( Check if two strings are permutation of each other ) 
private String sort(String word) { char[] content = word.toCharArray(); Arrays.sort(content); return new String(content); } private boolea...

2  Dos formas de aleatorias aleatoriamente las tarjetas  ( Two ways to randomly shuffle cards ) 
Aquí hay dos implementaciones que escribí para aleatorizar las tarjetas. El primer método ( dt5 ) Selecciona una tarjeta aleatoria, luego lo quita al frent...

25  Algoritmo para transformar una palabra a otra a través de palabras válidas  ( Algorithm to transform one word to another through valid words ) 
He estado practicando retroceso y quería saber cómo puedo mejorar mi código. Por ejemplo, no quiero usarlo global. Además, no estoy seguro de si mi código fun...

8  Simple GCD Utility en Java  ( Simple gcd utility in java ) 
i anteriormente discutido El rendimiento se refiere a diferentes algoritmos GCD. Escribí una simple clase de Java que implementa el algoritmo binario GCD. E...

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

1  Retire todos los nodos que no se encuentren en ningún camino con suma> = k  ( Remove all nodes which dont lie in any path with sum k ) 
Dado un árbol binario, una ruta completa se define como un camino desde la raíz a una hoja. La suma de todos los nodos en ese camino se define como la suma d...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...

35  Demasiados bucles en la aplicación de dibujo  ( Too many loops in drawing app ) 
Tengo un método que tiene muchos bucles: #ifndef __RUNES_STRUCTURES_H #define __RUNES_STRUCTURES_H /* Runes structures. */ struct Game { char board[2...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos