Q6 Unique Paths III - LeetCode 980

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());

    }
}