urban1

package com.mtk.problems.problemset;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Test {
  /**
   *
   *   11000
   *   11000
   *   00011
   *   00011
   *
   * 0,0 , 0,1, 1,1, 1,0
   * 0,0 , 0,1, 1,1, 1,0
   *
   */

  public static void main(String[] args) {

    int[][] arr = {{1,1,0,0,0},{1,1,0,0,0},{0,0,0,1,1},{0,0,0,1,1}};
    int res = findDistinctIslands(arr,4, 5);
    System.out.println(res);
  }

  private static int findDistinctIslands(int[][] arr,int m, int n) {

    List<String> sourceList = new LinkedList<>();
    for(int i=0;i<m;i++){
      for(int j=0;j<n;j++){
        if(arr[i][j]==1){
          sourceList.add(i+"_"+j);
        }
      }
    }

    Set<String> pathSet = new HashSet<>();
    Set<String> visited = new HashSet<>();
    Queue<String> q = new LinkedList<>();

    int x,y, sourceX, sourceY;
    String[] split;
    StringBuilder stringBuilder;
    String coord;
    for(String source: sourceList){
      stringBuilder = new StringBuilder();
      q.clear();
      q.add(source);

      split = source.split("[_]");
      sourceX = Integer.parseInt(split[0]);
      sourceY = Integer.parseInt(split[1]);

      while(!q.isEmpty()){
        coord = q.remove();
        if(visited.contains(coord)){
          continue;
        }
        split = coord.split("[_]");
        x = Integer.parseInt(split[0]);
        y = Integer.parseInt(split[1]);
        stringBuilder.append("#").append(x-sourceX).append("_").append(y-sourceY);
        visited.add(coord);
        if(x<m-1 && arr[x+1][y]==1){
          q.add((x+1)+"_"+y);
        }else if(x<m-1 && y<n-1 && arr[x+1][y+1]==1){
          q.add((x+1)+"_"+(y+1));
        }else if(y<n-1 && arr[x][y+1]==1){
          q.add(x+"_"+(y+1));
        }else if(x>0 && y<n-1 && arr[x-1][y+1]==1){
          q.add((x-1)+"_"+(y+1));
        }else if(x>0 && arr[x-1][y]==1){
          q.add((x-1)+"_"+y);
        }else if(x>0 && y>0 && arr[x-1][y-1]==1){
          q.add((x-1)+"_"+(y-1));
        }else if(y>0 && arr[x][y-1]==1){
          q.add((x)+"_"+(y-1));
        }else if(x<m-1 && y>0 && arr[x+1][y-1]==1){
          q.add((x+1)+"_"+(y-1));
        }
      }
      if(stringBuilder.length()>0) {
        pathSet.add(stringBuilder.toString());
      }
      System.out.println(stringBuilder.toString());
    }

    return pathSet.size();
  }

}