Number of Islands

 1 #define MAX 500
 2 
 3 struct vertex
 4 {
 5     int row;
 6     int col;
 7     vertex(int x, int y):row(x),col(y){
 8     }
 9 };
10 
11 class Solution {
12 private:
13 bool visit[MAX][MAX];
14 public:
15 
16     void BFSTraverse(vector<vector<char>>& grid, int i, int j)
17     {
18         visit[i][j] = true;
19         deque<vertex>m;
20         m.push_back(vertex(i,j));
21         while (!m.empty())
22         {
23             vertex v = m.front();
24             m.pop_front();
25             int mRow = v.row;
26             int mCol = v.col;
27             for (int k = 1; k <= 4; ++k)
28             {
29                 switch (k)
30                 {
31                     case 1:
32                         mRow = v.row-1;
33                         mCol = v.col;
34                         break;
35                     case 2:
36                         mRow = v.row+1;
37                         mCol = v.col;
38                         break;
39                     case 3:
40                         mRow = v.row;
41                         mCol = v.col-1;
42                         break;
43                     case 4:
44                         mRow = v.row;
45                         mCol = v.col+1;
46                         break;
47                 }
48                 if ( mRow >= 0 && mRow < grid.size() && mCol >=0 && mCol < grid[0].size() 
49                 && grid[mRow][mCol] == ‘1‘ && visit[mRow][mCol] == false)
50                 {
51                     visit[mRow][mCol] = true;
52                     m.push_back( vertex(mRow,mCol) );
53                 }
54             }
55         }
56     }
57     
58     int numIslands(vector<vector<char>>& grid) {
59         size_t row = grid.size();
60         if (row == 0)
61             return 0;
62         size_t col = grid[0].size();
63          //注意二维数组的初始化不可以直接用visit[MAX][MAX] = {false}，应采用for循环（memset函数似乎也可以）
64         for (int i = 0; i < row; ++i)
65         {
66             for (int j = 0; j < col; ++j)
67                 visit[i][j] = false;
68         }
69         int result = 0;
70         for (int i = 0; i < row; ++i)
71         {
72             for (int j = 0; j < col; ++j)
73             {
74                 if ( grid[i][j]==‘1‘ && visit[i][j] == false )
75                 {
76                     ++result;
77                     BFSTraverse(grid, i, j);
78                 }
79             }
80         }
81         return result;
82     }
83 };