leetcode 200 . 岛屿数量

链接 : 

. - 力index.php/tags-41973.html" >���（LeetCode）

广搜 : 

BFS 适合于解决两个点之间的最短路问题 ；

以起始点为中心一圈一圈的进行搜索 , 一旦遇到终点 ， 记录之前走过的结点就是一条最短路 ；

代码模板 : 

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向// grid 是地图，也就是一个二维数组// visited标记访问过的节点，不要重复访问// x,y 表示开始搜索节点的下标void bfs(vector& grid, vector& visited, int x, int y) {    queue que; // 定义队列    que.push({x, y}); // 起始节点加入队列    visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点    while(!que.empty()) { // 开始遍历队列里的元素        pair cur = que.front(); que.pop(); // 从队列取元素        int curx = cur.first;        int cury = cur.second; // 当前节点坐标        for (int i = 0; i = grid.size() || nexty = grid[0].size()) continue;  // 坐标越界了，直接跳过            if (!visited[nextx][nexty]) { // 如果节点没被访问过                que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点                visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问            }        }    }}

本题思路 : 

        是用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

本题代码 : 

class Solution {public:    int dx[4] = {-1 , 0 , 1 , 0} ;    int dy[4] = {0 , -1 , 0 , 1} ;    int n , m ;    void bfs(int x , int y , vector& grid , vector& tag){        queue que ;        que.push({x,y}) ;        tag[x][y] = true ;        while(!que.empty()){            auto tmp = que.front() ;            que.pop() ;            int tx = tmp.first , ty = tmp.second ;            for(int i=0;i=0 && ntx =0 && nty