1 class Solution {

 2

 3 private:

 4     int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

 5     int m,n;

 6     vector<vector<bool>> visited;

 7

 8     bool inArea( int x, int y){

 9         return x >= 0 && x < m && y >= 0 && y < n;

10     }

11

12     // 从grid[x][y]开始，进行floodfill

13     // 保证(x,y)合法，且grid[x][y]是没有被访问过的陆地

14     void dfs( vector<vector<char>>& grid, int x, int y ){

15

16         visited[x][y] = true;

17         for( int i = 0 ; i < 4 ; i ++ ){

18             int newx = x + d[i][0];

19             int newy = y + d[i][1];

20             // if语句保证访问合法，不需再写递归终止条件

21             if( inArea(newx, newy) && !visited[newx][newy] && grid[newx][newy] == '1')

22                 dfs( grid, newx, newy );

23         }

24         return;

25     }

26

27 public:

28     int numIslands(vector<vector<char>>& grid) {

29         m = grid.size();

30         if( m == 0 )

31             return 0;

32         n = grid[0].size();

33

34         visited = vector<vector<bool>>(m, vector<bool>(n,false));

35

36         int res = 0;

37         for( int i = 0 ; i < m ; i ++ )

38             for( int j = 0 ; j < n ; j ++ )

39             if( grid[i][j] == '1' && !visited[i][j] ){

40                 res ++;

41                 dfs( grid, i, j );

42             }

43         return res;

44     }

45 };