HashMap and DFS


  • 0
    T
    public class Solution {
        public int NumDistinctIslands(int[,] grid) {
            int rows = grid.GetLength(0);
            int cols = grid.GetLength(1);
            var visited = new HashSet<string>();
            int result = 0;
            int b = 3;
            for(int i = 0;i<rows;i++){
                for(int j = 0;j<cols;j++){
                    if(grid[i,j] == 1){
                        int[] r = new int[]{i,j,i,j};
                        Helper(grid,i,j,rows,cols,r,b);
                        string printStr = Print(r,grid,b);
                        //Console.WriteLine(printStr);
                        if(visited.Add(printStr))
                            result++;
                        b++;
                    }
                }
            }
            return result;
        }
        
        private string Print(int[] r,int[,] grid,int b){
            StringBuilder sb = new StringBuilder();
            for(int i = r[0];i<=r[2];i++){
                for(int j = r[1];j<=r[3];j++){
                    if(grid[i,j] == b)
                        sb.Append(1+",");
                    else
                        sb.Append(0+",");
                }
                sb.Append("|");
            }
            return sb.ToString();
        }
        
        // 0 : left
        // 1 : top
        // 2 : right
        // 3 : bottom
        private void Helper(int[,] grid,int i,int j,int rows,int cols,int[] r,int b){
            if(i<0||j<0||i>=rows||j>=cols||grid[i,j] != 1)
                return;
            
            r[0] = Math.Min(r[0],i);
            r[1] = Math.Min(r[1],j);
            r[2] = Math.Max(r[2],i);
            r[3] = Math.Max(r[3],j);
            
            grid[i,j] = b;
            
            Helper(grid,i+1,j,rows,cols,r,b);
            Helper(grid,i,j+1,rows,cols,r,b);
            Helper(grid,i,j-1,rows,cols,r,b);
            Helper(grid,i-1,j,rows,cols,r,b);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.