//{ 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"); } }