Q10 Number of Distinct Islands | Practice | GeeksforGeeks

//{ Driver Code Starts
// Initial Template for Java

import java.util.*;
import java.lang.*;
import java.io.*;

// Position this line where user code will be pasted.

class GFG {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] grid = new int[n][m];

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

                for (int j = 0; j < m; j++) {
                    grid[i][j] = sc.nextInt();
                }
            }

            Solution ob = new Solution();
            int ans = ob.countDistinctIslands(grid);
            System.out.println(ans);
        }
    }
}
// } Driver Code Ends


// User function Template for Java

class Solution {

    int countDistinctIslands(int[][] grid) {
        /*Q3 of graph playlist , we will find GCC and store the structure in form
        of string in a hashmap , if the same structure appears it wont be added in
        the hashmap 
        -> we will also add a character in string when backtracking (*edge case*) 
        -> we will return length of hashmap in the end
        */
        int m = grid.length , n = grid[0].length ;
    
        HashSet<String> set = new HashSet<>();
        for(int i =0 ;i < m ; i++){
            for(int j = 0 ;j < n ;j++){
                
                if(grid[i][j] == 1){
                    psf = new StringBuilder();
                    psf.append("x");
                    dfs(grid , i , j , m, n);
                    // System.out.println(psf);
                    set.add(psf.toString());
                }
                
            }
        }
        return set.size();
    }
    // up right down left
    public StringBuilder psf = new StringBuilder(); //path so far = structure
    public void dfs(int[][] grid , int row , int col , int m , int n ){
        //we need to make proactive call as we have to handle for psf
        
        grid[row][col] = 0; //marking 
        if(row-1 >= 0 && grid[row-1][col] == 1){
            psf.append("u");
            dfs(grid , row-1 , col , m , n);
        }
        
        if(col+1 < n && grid[row][col+1] == 1){
            psf.append("r");
            dfs(grid , row , col+1 , m , n);
        }
        
        if(row+1 < m && grid[row+1][col] == 1){
            psf.append("d");
            dfs(grid , row+1 , col , m , n);
        }
        
        if(col-1 >= 0 && grid[row][col-1] == 1){
            psf.append("l");
            dfs(grid , row , col-1 , m , n);
        }
        
        //adding backtracking character
        psf.append("z");
    }
}