Java 2 direction check with little backtrack


  • 0
    C

    I tried to read the grid by line, and save every result to dp[] array. island is for current island Index, count is for same island, which should be delete.

    public class Solution {
        public int numIslands(char[][] grid) {
            if(grid.length==0) return 0;
            int[] dp= new int[grid[0].length];
            int island=0;
            int count=0;
            for(int x=0;x<grid.length;x++)
            {
                for(int y=0;y<grid[0].length;y++)
                {
                    if(grid[x][y]=='1')
                    {
                        if(dp[y]==0&&(y==0||dp[y-1]==0))
                            dp[y]=++island;
                        else if (dp[y]!=0&&(y!=0&&dp[y-1]!=0))
                        {
                            if (dp[y]!=dp[y-1])
                            {
                                int min=dp[y]<dp[y-1]?dp[y]:dp[y-1];
                                int max=dp[y]>dp[y-1]?dp[y]:dp[y-1];
                                count++;
                                for(int i=0;i<grid[0].length;i++)
                                    if(dp[i]==max) dp[i]=min;
                            }
                        }
                        else if (dp[y]!=0||(y!=0&&dp[y-1]!=0))
                            dp[y]=dp[y]!=0?dp[y]:dp[y-1];
                    }
                    else dp[y]=0;
                }
            }
    
            return island-count;
        }
    }
    

    This is my first comment, Thank you.


Log in to reply
 

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