200 - Number of Islands

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:

11110
11010
11000
00000

Answer: 1
Example 2:

11000
11000
00100
00011

Answer: 3
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Hide Tags
Depth-first Search Breadth-first Search Union Find
Hide Similar Problems
(M) Surrounded Regions

毫无疑问就是遍历了，DFS吧，一开始脑抽只做了右边下边两个方向，居然是超时，怪异。
后来改到一个case才意识到NND是四面佛，改到四面就好了。
不需要辅助的数组了，只需要一个counter，把counter的值填到原来的矩阵里就可以了。（保险起见填入的是负数。）

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rst=0;

        for(int ii=0; ii<grid.size(); ++ii)
            for(int jj=0; jj<grid[0].size(); ++jj)
                if('1'==grid[ii][jj])
                    dfs(grid, grid.size(), grid[0].size(), ii, jj, --rst);

        return 0-rst;
    }
   
    void dfs(vector<vector<char>>& g, int sz, int zz, int x, int y, int count)
    {
        if(0>x || sz<=x || 0>y || zz<=y || (x<sz && y<zz && '1'!=g[x][y]))
            return;

        g[x][y] = (char)count;

        dfs(g, sz, zz, x, y+1, count);
        dfs(g, sz, zz, x+1, y, count);
        dfs(g, sz, zz, x, y-1, count);
        dfs(g, sz, zz, x-1, y, count);
    }
};
8 ms.