Very classic search question. Through the number group, starting from each 1, the depth-first search is conducted to see whether all the positions connected to the current position are all 1 (that is, the land connected to it). An additional Boolean array visited is used to record whether the elements of each position have been visited. Each traversed position visited is marked as true.
The code is as follows:
class Solution { public: vector<vector<bool>> visited; int res = 0, rows, cols; int dx[4] = {1, 0, 0, -1}, dy[4] = {0, 1, -1, 0}; // The two arrays represent x, Void DFS(int x, int y, vector<vector<bool>>& visited, vector<vector<char>>& grid) {visited[x][y] = true; for(int i = 0; i < 4; Int newX = x + dx[I], newY = y + dy[I]; / / calculate the next position if (newX < 0 | | newX > = rows | | newY < 0 | | newY > = cols | | grid [newX] [newY]! = '1' | | visited [newX] [newY]) {/ / if the new location cross-border or not for 1 or already visited, just skip the continue; } DFS(newX, newY, visited, grid); / / otherwise continue to look for unicom from the next position 1}} int numIslands (vector < vector < char > > & grid) {if (grid. The size () = = 0 | | grid [0]. The size () = = 0) {return 0; } rows = grid.size(), cols = grid[0].size(); visited = vector<vector<bool>>(rows, vector<bool>(cols, false)); for(int i = 0; i < rows; ++i) { for(int j = 0; j < cols; ++j) { if(grid[i][j] == '1' && ! [I][j]) {// We find a land starting point that has not been visited before, update the number of answers, start DFS from this location, find all the 1 connected with it, and update the visited array ++res; DFS(i, j, visited, grid); } } } return res; }};Copy the code