Bitmap

There is given a rectangular bitmap of size n*m. Each pixel of the bitmap is either white or black, but at least one is white. The pixel in i-th line and j-th column is called the pixel (i,j). The distance between two pixels p1=(i1,j1) and p2=(i2,j2) is defined as:


d(p1,p2)=|i1-i2|+|j1-j2|.


Task


Write a program which:
reads the description of the bitmap from the standard input,
for each pixel, computes the distance to the nearest white pixel,
writes the results to the standard output.
Input


The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case there is a pair of integer numbers n, m separated by a single space, 1<=n <=182, 1<=m<=182. In each of the following n lines of the test case exactly one zero-one word of length m, the description of one line of the bitmap, is written. On the j-th position in the line (i+1), 1 <= i <= n, 1 <= j <= m, is '1' if, and only if the pixel (i,j) is white.
Output


In the i-th line for each test case, 1<=i<=n, there should be written m integers f(i,1),...,f(i,m) separated by single spaces, where f(i,j) is the distance from the pixel (i,j) to the nearest white pixel.


Example
Sample input:
1
3 4
0001
0011
0110


Sample output:
3 2 1 0
2 1 0 0
1 0 0 1

https://www.spoj.pl/problems/BITMAP/ 

public class BitMap 
{
   public static void main( String args[] ) throws Exception
   {
      // Buffer de caracteres donde se guardara la salida del programa
      char[] salida = new char[ 200000  ];

      //  Tamanio de la salida ( cantidad de caracteres )
      int tamanio, longitud;
      String cadena;

      int numFil, numCol;
      int[][] matriz;
      int distancia, pixel, cabezaCola, fondoCola, f, c;

      // Cola que servira para realizar el algoritmo de busqueda en anchura
      int colaF[] = new int[ 35000 ];
      int colaC[] = new int[ 35000 ];

      int numCasos = sig();

      for( int i = 0; i < numCasos; i ++ )
      {
         numFil = sig();  numCol = sig();

         matriz = new int[ numFil + 2 ][ numCol + 2 ];
         fondoCola = cabezaCola = 0;

         /**
         * Leemos los datos de la matriz, como cada dato consta
         * de un solo digito es suficiente usar la funcion read()
         */
         for( f = 1; f <= numFil; f ++ )
         {
            for( c = 1; c <= numCol; c ++ )
            {
               pixel = System.in.read();

               // Se encontro un pixel, y lo marcamos con 1, ademas
               // lo anadimos a la cola
               if( pixel == 49 )
               {
                  matriz[ f ][ c ] = 1;

                  colaF[ cabezaCola ] = f;
                  colaC[ cabezaCola ] = c;
                  cabezaCola ++;
               }
            }

            // Nos saltamos el fin de linea ( '\n' )
            System.in.read();
         }

         /**
         * Marcamos todos los bordes de la matriz con 1, esto 
         * nos ayudara a evitar tener que estar comparando si
         * las coordenadas de un pixel ( fila y columna ) se 
         * encuentran dentro del rango de la matriz
         */
         for( f = 0; f < matriz.length; f ++ )
         {
            matriz[ f ][ 0 ] = 1;
            matriz[ f ][ matriz[0].length - 1 ] = 1;
         }

         for( c = 0; c < matriz[0].length; c ++ )
         {
            matriz[ 0 ][ c ] = 1;
            matriz[ matriz.length - 1 ][ c ] = 1;
         }

         /**
         * Realizamos el algoritmo de busqueda en anchura.
         */
         while( cabezaCola != fondoCola )
         {
            f = colaF[ fondoCola ];
            c = colaC[ fondoCola ];

            fondoCola ++;

            distancia = matriz[ f ][ c ] + 1;

            /*
            * Para cada caso verificamos si el pixel aun no ha sido marcado,
            * si es asi lo marcamos, y anadimos ese pixel a la cola para despues
            * poder procesar los pixeles adyacentes a este.
            */
            if( matriz[ f - 1 ][ c ] == 0 )
            {
               matriz[ f - 1 ][ c ] = distancia;
               colaF[ cabezaCola ] = f - 1;
               colaC[ cabezaCola ] = c;
               cabezaCola ++;
            }

            if( matriz[ f + 1 ][ c ] == 0 )
            {
               matriz[ f + 1 ][ c ] = distancia;
               colaF[ cabezaCola ] = f + 1;
               colaC[ cabezaCola ] = c;
               cabezaCola ++;
            }

            if( matriz[ f ][ c - 1 ] == 0 )
            {
               matriz[ f ][ c - 1 ] = distancia;
               colaF[ cabezaCola ] = f;
               colaC[ cabezaCola ] = c - 1;
               cabezaCola ++;
            }

            if( matriz[ f ][ c + 1 ] == 0 )
            {
               matriz[ f ][ c + 1 ] = distancia;
               colaF[ cabezaCola ] = f;
               colaC[ cabezaCola ] = c + 1;
               cabezaCola ++;
            }
         }

         tamanio = 0;

         for(  f = 1; f < numFil + 1; f ++ )
         {
            for( c = 1; c < numCol; c ++ )
            {
               // Obtenemos la representacion en cadena del elemento
               cadena = Integer.toString( matriz[ f ][ c ] - 1 );
               longitud = cadena.length();

               // Copiamos los caracteres de la cadena al buffer de salida
               cadena.getChars( 0, longitud, salida, tamanio );
               tamanio = tamanio + longitud;

               // Anadimos el caracter de espacio
               salida[ tamanio ++ ] = ' ';
            }

            // Obtenemos la representacion en cadena del elemento
            cadena = Integer.toString( matriz[ f ][ c ] - 1 );
            longitud = cadena.length();

            // Copiamos los caracteres de la cadena al buffer de salida
            cadena.getChars( 0, longitud, salida, tamanio );
            tamanio = tamanio + longitud;

            // Anadimos el caracter de fin de linea
            salida[ tamanio ++ ] = '\n';
         }

         // Mostramos la matriz de distancias para el caso actual
         System.out.print( new String( salida, 0, tamanio ) );

         // Nos saltamos la linea en blanco
         System.in.read();
      }
   }
   public static int sig() throws Exception
   {
      int val = 0;
      int car = System.in.read();

      while( car > 47 && car < 58 )
      {
         val = val * 10 + ( car - 48 );
         car = System.in.read();
      }

      return val;
   }
}