島の数-BFS

Number Islands Bfs

タイトル（leetcodeから）：

アイデア。一度に1つの土地に隣接するすべての土地を検索します。キューが空に見えることを知っている、ans +1。
コード：

class Solution { public: vector<vector<char>> grid queue<pair<int,int>>que //Determine whether it is legal land bool isIsland(int x,int y){ return 0<=x && x<grid.size() && 0<=y && y<grid[0].size()//Within the boundary && grid[x][y]=='1'//Value is 1 } //Put the land next to the land into the exploration queue (four directions up, down, left, and right) void checkAndEnqueue(int x,int y){ if(isIsland(x-1,y)) que.push(make_pair(x-1,y)) if(isIsland(x+1,y)) que.push(make_pair(x+1,y)) if(isIsland(x,y-1)) que.push(make_pair(x,y-1)) if(isIsland(x,y+1)) que.push(make_pair(x,y+1)) } int numIslands(vector<vector<char>>& grid) { this->grid=grid if(grid.empty()) return 0 int m=grid.size(),n=grid[0].size(),ans=0//The length and width of the given map for(int i=0i<mi++){ for(int j=0j<nj++){ //First encounter with land if(grid[i][j]=='1'){ que.push(make_pair(i,j))//Put this point into the queue ans++ //Explore all connected land on this island while(!que.empty()){ pair<int,int> root=que.front() que.pop()//The first out of the queue int x=root.first,y=root.second if(grid[x][y]=='0')continue//Zero out directly //Mark as explored grid[x][y]='0' //Put the connected land into the expedition queue checkAndEnqueue(x,y) } } } } return ans } }