Leetcode 200.Number of Islands

\\bfs
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ret = 0;
        if(grid.empty()||grid[0].empty()) return ret;
        int dx[4]={-1,0,1,0};
        int dy[4]={0,1,0,-1};      
        for(int i =0;i < grid.size();++i){
            for(int j = 0; j < grid[0].size();++j){
                if(grid[i][j]=='0') continue;
                ret++;
                queue<pair<int,int >> nbs;
                nbs.push(make_pair(i,j));
                grid[i][j]='0';
                while(!nbs.empty()){
                    pair<int,int> cur = nbs.front();
                    nbs.pop();
                    for(int k=0;k<4;++k){
                        pair<int,int> nb = make_pair(cur.first+dx[k],cur.second+dy[k]);
                        if(inBound(nb,grid) && grid[nb.first][nb.second]=='1'){
                             grid[nb.first][nb.second]='0';
                             nbs.push(nb);
                        }
                    }
                }
            }
        }
        return ret;
    }
    private: 
    bool inBound(pair<int,int> cur, vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();  
        return cur.first >= 0 && cur.first < n && cur.second >= 0 && cur.second < m;
    }
};

\\floodfill
class Solution {
private:
    int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};\\不是顺时针，随便写的，其他情况需要注意用不用排序
    int m,n;
    vector<vector<bool>> visited;

    bool inArea( int x , int y ){
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    // 从grid[x][y]的位置开始,进行floodfill
    // 保证(x,y)合法,且grid[x][y]是没有被访问过的陆地
    void dfs( vector<vector<char>>& grid , int x , int y ){

        //assert( inArea(x,y) );
        visited[x][y] = true;
        //没有回溯的过程(set visited to false)这是因为floodfill的目的就是把所有的islands都标记上而不是去寻找某一个序列或者值
        for( int i = 0 ; i < 4 ; i ++ ){
            int newx = x + d[i][0];
            int newy = y + d[i][1];
            if( inArea(newx, newy) && !visited[newx][newy] && grid[newx][newy] == '1' )
                dfs( grid , newx , newy );
        }

        return;
    }
public:
    int numIslands(vector<vector<char>>& grid) {

        m = grid.size();
        if( m == 0 )
            return 0;
        n = grid[0].size();
        visited = vector<vector<bool> >(m,vector<bool>(n,false));

        int res = 0;
        for( int i = 0 ; i < m ; i ++ )
            for( int j = 0 ; j < n ; j ++ )
                if( grid[i][j] == '1' && !visited[i][j] ){
                    dfs( grid , i , j );
                    res ++;
                }
        return res;
    }
};

• https://leetcode.com/problems/number-of-islands/description/
• http://www.cnblogs.com/grandyang/p/4402656.html