class Solution { public int uniquePathsIII(int[][] grid) { /* basically this is a question of hamiltonian path in graphs find position of 1 and send it to dfs function if there exists a path with only one visit per node we will increase the count */ int m = grid.length , n = grid[0].length; //finding position of 1 and count no. of -1 int pos_x = 0 , pos_y = 0; //finding position of 1 int count = 0; //calculating no. of -1 HashSet<String> visited = new HashSet<>(); for(int i = 0 ; i< m ; i++){ for(int j = 0 ; j < n ;j++){ if(grid[i][j] == 1){ pos_x = i ; pos_y = j ; } else if(grid[i][j] == -1) count ++; } } //finding total no.of tiles without -1 count = m*n - count -1 ; dfs(grid , pos_x , pos_y , visited , count); return paths; } public int paths = 0; public void dfs(int[][] grid , int i , int j , HashSet<String> visited , int count){ //base case if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || visited.contains(i + "*" + j) || grid[i][j] == -1) return ; //when at destination , check if all the vertices are covered if(grid[i][j] == 2){ System.out.println(visited.size() + "->" + count); if(visited.size() == count) paths++; return; } StringBuilder sb = new StringBuilder(); sb.append(i + "*" + j); visited.add(sb.toString()); //calls for 4 directions dfs(grid , i , j+1 , visited , count); dfs(grid , i , j-1 , visited , count); dfs(grid , i+1 , j , visited , count); dfs(grid , i-1 , j , visited , count); visited.remove(sb.toString()); } }