Code & Func

第37天。

今天的题目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

解法相当简单，只要遍历所有点，然后如何当前点是1,就将计数加一，然后进行扩展，所谓的扩展就是将当前点的值至为0,然后向上下左右进行查找，如果还是1就递归调用扩展。

1
    int numIslands(vector<vector<char>>& grid) {
2
        if (grid.size() == 0 || grid[0].size() == 0) return 0;
3
        int count = 0;
4

5
        for(int i = 0;i < grid.size();i++) {
6
            for(int j = 0;j < grid[0].size();j++) {
7
                if (grid[i][j] == '1') {
8
                    cout << "(" << i << "," << j << ")\n";
9
                    count++;
10
                    expend(grid,i,j);
11
                }
12
            }
13
        }
14
        return count;
15
    }
14 collapsed lines
16
    void expend(vector<vector<char> > &grid,int x,int y) {
17
        if ( x < 0 || y < 0 ||
18
            x >= grid.size() || y >= grid[0].size() ||
19
           grid[x][y] == '0' ) return;
20
        //cout << x << " " << y << endl;
21
        grid[x][y] = '0';
22
        expend(grid,x-1,y);
23
        expend(grid,x+1,y);
24
        expend(grid,x,y-1);
25
        expend(grid,x,y+1);
26
    }
27
``
28

29
因为`dicuss`中的做法都是一样的，所以就不贴`dicuss`的代码了。