C Solution with DFS


  • 0
    L

    Maybe a little disordered, because I didn't implement DPS properly at first and then revised it.
    .

     int numIslands(char** grid, int gridRowSize, int gridColSize) {
            if(grid==NULL||(gridRowSize==0&&gridColSize==0))
               return 0;
            int toSize=gridRowSize*gridColSize;
            int curID=0;
            int result=0;
            
            curID=nextIsland(curID,grid,gridRowSize,gridColSize);
            while(curID!=-1)
            {  
                boundIsland(curID,&grid,gridRowSize,gridColSize);
                curID++;
                curID=nextIsland(curID,grid,gridRowSize,gridColSize);
                result++;
            }
            return result;
            
        }
        
        // To find next island ID tagged with '1', if can not find one, return -1;
        int nextIsland(int curID, char** grid, int gridRowSize, int gridColSize){
            int toSize=gridRowSize*gridColSize;
            while(curID<toSize)
            {
                int rowID=curID/gridColSize;
                int colID=curID%gridColSize;
                if(grid[rowID][colID]=='1')
                   return curID;
                curID++;
            }
            return -1;
        }
        
        //To determine the bound of an island, change every connected '1' into '2'
        void boundIsland(int curID, char*** gridPtr, int gridRowSize, int gridColSize){
            
            int rowID=curID/gridColSize;
            int colID=curID%gridColSize;
            (*gridPtr)[rowID][colID]='2';
            
            if(rowID>0&&(*gridPtr)[rowID-1][colID]=='1')
               boundIsland(curID-gridColSize,gridPtr,gridRowSize,gridColSize);
            if(rowID<(gridRowSize-1)&&(*gridPtr)[rowID+1][colID]=='1')
               boundIsland(curID+gridColSize,gridPtr,gridRowSize,gridColSize); 
            if(colID>0&&(*gridPtr)[rowID][colID-1]=='1')
               boundIsland(curID-1,gridPtr,gridRowSize,gridColSize);
            if(colID<(gridColSize-1)&&(*gridPtr)[rowID][colID+1]=='1')
               boundIsland(curID+1,gridPtr,gridRowSize,gridColSize);
            return;
        }

Log in to reply
 

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