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 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| class Solution { public:
vector<vector<int>> vis; int rows; int cols; int result; int* rdir; int* cdir; void DFS(vector<vector<char>>& grid, int r, int c) { if (vis[r][c]) return; if (grid[r][c] == '1') { vis[r][c] = true; for(int k = 0; k < 4; ++k) { int i = r + rdir[k]; int j = c + cdir[k]; if(i >=0 && i < rows && j >= 0 && j < cols && vis[i][j] == 0) DFS(grid,i,j); } } }
int numIslands(vector<vector<char>>& grid) { result = 0; rows = grid.size(); if (rows == 0) return 0; cols = grid[0].size(); if (cols == 0) return 0; vis = vector<vector<int>>(rows,vector<int>(cols,0)); int rdirs[] = {0,0,1,-1}; int cdirs[] = {1,-1,0,0}; rdir = rdirs; cdir = cdirs;
for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (vis[i][j] == 0 && grid[i][j] == '1') { ++result; DFS(grid,i,j); } } } return result; } };
|