Spoj Problem BITMAP- Bitmap[Java Solution]  using BFS

Problem Statement:-http://www.spoj.com/problems/BITMAP/

Hint:- Apply BFS.

Perform the BFS on the nodes where 1 is present and to elaborate(open) those nodes which are not 1 in BITMAP and calculate the distance and sotred in 2d array(i.e here sol[][]).If the solution array previously had any value(other than -1 i.e initially all -1) then minimum should be stored.

Java Program:-

/**

 * @(#)BITMAP.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2015/12/14

 */

import java.io.*;

import java.util.*;

class Node{

     int x;

     int y;

     int value;

    

     @Override

     public boolean equals(Object obj){

     Node n=(Node)obj;

     return this.x==n.x&&this.y==n.y;

     }

}

class BITMAP {

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

   

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

   

    int T=Integer.parseInt(br.readLine());

   

    while(T--!=0){

   

    String str[]=br.readLine().split(" ");

   

    int n=Integer.parseInt(str[0]);

    int m=Integer.parseInt(str[1]);

   

    Node bitmap[][]=new Node[n][m];

   

    int sol[][]=new int[n][m];

    String temp;

    Node temp2;

    int c=1;

    for(int i=0;i<n;i++){

    temp=br.readLine();

    for(int j=0;j<m;j++){

    temp2=new Node();

    temp2.x=i;

    temp2.y=j;

    temp2.value=Integer.parseInt(temp.charAt(j)+"");

    bitmap[i][j]=temp2;

    sol[i][j]=-1;

    }

    }

    for(int i=0;i<n;i++){

    for(int j=0;j<m;j++){

    if(bitmap[i][j].value==1){

    sol[i][j]=0;

    bfs(bitmap,bitmap[i][j],sol);

    }

    }

    }

    StringBuilder sb=new StringBuilder();

    for(int i=0;i<n;i++){

    for(int j=0;j<m;j++){

    //System.out.print(sol[i][j]+" ");

    sb.append(sol[i][j]+" ");;

    }

    //System.out.println();

    sb.append("\n");

    }

    System.out.print(sb);

    br.readLine();

   

    }

   

    }

    

    

    public static void bfs(Node bitmap[][],Node root,int sol[][]){

   

    int visited[][]=new int[bitmap.length][bitmap[0].length];

    Queue<Node> Q=new LinkedList<Node>();

    Q.offer(root);

   

    visited[root.x][root.y]=1;

    Node temp;

    int x1,y1,d;

    while(!Q.isEmpty()){

    temp=Q.poll();

    x1=temp.x;y1=temp.y;

   

    if(x1-1>=0&&visited[x1-1][y1]==0&&bitmap[x1-1][y1].value!=1){

    Q.offer(bitmap[x1-1][y1]);

    visited[x1-1][y1]=1;

    d=(int)Math.abs((x1-1)-root.x)+(int)Math.abs(y1-root.y);

    if(sol[x1-1][y1]==-1){

    sol[x1-1][y1]=d;

    }else{

    sol[x1-1][y1]=Math.min(sol[x1-1][y1],d);

    if(sol[x1-1][y1]<d){

    Q.remove(bitmap[x1-1][y1]);

    }

    }

    }

    if(y1-1>=0&&visited[x1][y1-1]==0&&bitmap[x1][y1-1].value!=1){

    Q.offer(bitmap[x1][y1-1]);

    visited[x1][y1-1]=1;

    d=(int)Math.abs(x1-root.x)+(int)Math.abs((y1-1)-root.y);

    if(sol[x1][y1-1]==-1){

    sol[x1][y1-1]=d;

    }else{

    sol[x1][y1-1]=Math.min(sol[x1][y1-1],d);

    if(sol[x1][y1-1]<d){

    Q.remove(bitmap[x1][y1-1]);

    }

    }

    }

    if(y1+1<bitmap[0].length&&visited[x1][y1+1]==0&&bitmap[x1][y1+1].value!=1){

    Q.offer(bitmap[x1][y1+1]);

    visited[x1][y1+1]=1;

    d=(int)Math.abs(x1-root.x)+(int)Math.abs((y1+1)-root.y);

    if(sol[x1][y1+1]==-1){

    sol[x1][y1+1]=d;

    }else{

    sol[x1][y1+1]=Math.min(sol[x1][y1+1],d);

    if(sol[x1][y1+1]<d){

    Q.remove(bitmap[x1][y1+1]);

    }

    }

    }

    if(x1+1<bitmap.length&&visited[x1+1][y1]==0&&bitmap[x1+1][y1].value!=1){

    Q.offer(bitmap[x1+1][y1]);

    visited[x1+1][y1]=1;

    d=(int)Math.abs((x1+1)-root.x)+(int)Math.abs(y1-root.y);

    if(sol[x1+1][y1]==-1){

    sol[x1+1][y1]=d;

    }else{

    sol[x1+1][y1]=Math.min(sol[x1+1][y1],d);

    if(sol[x1+1][y1]<d){

    Q.remove(bitmap[x1+1][y1]);

    }

    }

    }

    }

   

   

   

    }

    

    

    

}

Input:-

1
3 4
0001
0011
0110

Output:-

3 2 1 0
2 1 0 0
1 0 0 1

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------