Simple C++ DFS Using Graph Coloring


  • 0
    L

    The idea is based on graph coloring, we use different colors to color the same island, the number of islands = the number of colors we use.
    The code is as follow:

    class Solution {
    public:
        vector<vector<int>> book;//mark if a point has been visited or not,it's global
        int numIslands(vector<vector<char>>& grid) {
            int color=0;//use number from -1 to -n to color the graph, initially set it to be 0
            int row=grid.size();
            if(row==0)return 0;
            int col=grid[0].size();
            vector<vector<int>> init(row,vector<int>(col,0));//use it to initialize book[]
            book=init;
            for(int i=0;i<row;i++){//use dfs on any point of '1'
                for(int j=0;j<col;j++){
                    if(grid[i][j]=='1'){
                        color--;
                        book[i][j]=1;//now the point has been visited, mark it
                        dfs(grid,i,j,color);
                    }   
                }
            }
            return -color;//each island needs a color, number of islands = number of colors = -color(since it starts from 0)
        }
        void dfs(vector<vector<char>>& grid,int x,int y,int color){
            int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//different directions
            int row=grid.size();
            int col=grid[0].size();
            grid[x][y]=color;//color the current point
            for(int k=0;k<4;k++){//try 4 different directions
                int tx=x+next[k][0];
                int ty=y+next[k][1];
                if(tx<0||tx>row-1||ty<0||ty>col-1)//the border
                    continue;
                if(grid[tx][ty]=='1'&&book[tx][ty]==0){//if it's '1' and hasn't been visited yet
                    book[tx][ty]=1;//visit it
                    dfs(grid,tx,ty,color);//continue to search
                }
            }
        }
    };
    

Log in to reply
 

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