lc200-Number of Islands

發表於   |   0 comments   |   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    vector<int> visited;
    int m;
    int n;
public:
    int flatten(int i, int j) {
        return i*n+j;
    }
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        int cnt = 0;
        if (m) {
            n = grid[0].size();
            for (int i = 0; i < m*n; i++) {
                visited.push_back(0);
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1' && !visited[flatten(i,j)]) {
                        dfs(i,j,grid);
                        cnt++;
                    }
                    
                }
            }
        }
        return cnt;
    }
    void dfs(int i, int j, vector<vector<char>>& grid) {
        visited[flatten(i,j)] = 1;
//        cout << "dfs at "<<i<<" "<<j<<endl;
        if (i > 0 && grid[i-1][j] == '1' && !visited[flatten(i-1,j)])  dfs(i-1,j, grid);
        if (i < m-1 && grid[i+1][j] == '1' && !visited[flatten(i+1,j)])  dfs(i+1,j, grid);
        if (j > 0 && grid[i][j-1] == '1' && !visited[flatten(i,j-1)])  dfs(i,j-1, grid);
        if (j < n-1 && grid[i][j+1] == '1' && !visited[flatten(i,j+1)])  dfs(i,j+1, grid);
    }
};