广度优先搜索(使用Java和C++实现)

200.岛屿数量

传送门

java代码如下

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
class Solution {
    int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    class position{
        int x;
        int y;
        position(int x, int y){this.x=x;this.y=y;};
    }
    void bfs(boolean[][] visited, char[][] grid, int i, int j, int m, int n){
        ArrayDeque<position> q = new ArrayDeque<position>();
        visited[i][j] = true;
        q.addLast(new position(i,j));
        int nextx,nexty;
        while(!q.isEmpty()){
            position p = q.removeFirst();
            for(int k=0; k<4; k++){
                nextx = p.x+dir[k][0];
                nexty = p.y+dir[k][1];
                if(nextx<0 || nextx>=m || nexty<0 || nexty>=n){
                    continue;
                }
                if(!visited[nextx][nexty] && grid[nextx][nexty]=='1'){
                    q.addLast(new position(nextx,nexty));
                    visited[nextx][nexty] = true;
                }
            }
        }
    }
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int cnt = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!visited[i][j] && grid[i][j]=='1'){
                    cnt++;
                    bfs(visited,grid,i,j,m,n);
                }
            }
        }
        return cnt;
    }
}

C++代码如下

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
class Solution {
private:
    int dir[4][2] = {-1,0,1,0,0,-1,0,1};
    void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int i, int j){
        visited[i][j] = true;
        queue<pair<int,int>> q;
        q.push({i,j});
        while(!q.empty()){
            pair<int, int> cur = q.front();
            q.pop();
            int x = cur.first;
            int y = cur.second;
            for(int di=0; di<4; di++){
                int nextx = x + dir[di][0];
                int nexty = y + dir[di][1];
                if(nextx<0 || nextx>=grid.size() || nexty<0 || nexty>=grid[0].size())
                    continue;
                if(grid[nextx][nexty]=='1' && !visited[nextx][nexty]){
                    q.push({nextx,nexty});
                    visited[nextx][nexty] = true;
                }
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int cnt = 0;
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<bool>> visited(row,vector<bool>(col,false));
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(grid[i][j]=='1' && !visited[i][j]){
                    cnt++;
                    bfs(grid,visited,i,j);
                }
            }
        }
        return cnt;
    }
};

1020.飞地的数量

传送门

Java

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
class Solution {
    int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    class position{
        int x;
        int y;
        position(int x, int y){this.x=x;this.y=y;};
    }
    int bfs(boolean[][] visited, int[][] grid, int i, int j, int m, int n){
        ArrayDeque<position> q = new ArrayDeque<position>();
        visited[i][j] = true;
        q.addLast(new position(i,j));
        int nextx,nexty;
        int size = 1;
        boolean flag = false;// 标记是否到了边界
        while(!q.isEmpty()){
            position p = q.removeFirst();
            for(int k=0; k<4; k++){
                nextx = p.x+dir[k][0];
                nexty = p.y+dir[k][1];
                if(nextx<0 || nextx>=m || nexty<0 || nexty>=n){
                    flag = true;
                    continue;//不能提前退出, 因为必须把这个岛屿的所有格子都标记一下
                }
                if(!visited[nextx][nexty] && grid[nextx][nexty]==1){
                    q.addLast(new position(nextx,nexty));
                    size++;
                    visited[nextx][nexty] = true;
                }
            }
        }
        return flag?0:size;
    }
    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int cnt = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!visited[i][j] && grid[i][j]==1){
                    cnt += bfs(visited,grid,i,j,m,n);
                }
            }
        }
        return cnt;
    }
}

C++解法, 另一种思路, 可以先标记和边界有连接的岛屿, 再统计其他岛屿, 缺点需要绕着边界走一次int go[4][2] = {0,1,1,0,0,-1,-1,0};, 如果怕麻烦, 可以改造成如上Java用的方法, 在超出边界的时候标记flag为true, 随后接着标记岛屿所有格子, 当flag==true时返回一个0

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
52
53
54
55
56
57
58
59
60
61
62
class Solution {
private:
    int dir[4][2] = {-1,0,1,0,0,-1,0,1};
    int bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j){
        int size = 1;
        visited[i][j] = true;
        queue<pair<int,int>> q;
        q.push({i,j});
        while(!q.empty()){
            pair<int, int> cur = q.front();
            q.pop();
            int x = cur.first;
            int y = cur.second;
            for(int di=0; di<4; di++){
                int nextx = x + dir[di][0];
                int nexty = y + dir[di][1];
                if(nextx<0 || nextx>=grid.size() || nexty<0 || nexty>=grid[0].size())
                    continue;
                if(grid[nextx][nexty]==1 && !visited[nextx][nexty]){
                    q.push({nextx,nexty});
                    size++;
                    visited[nextx][nexty] = true;
                }
            }
        }
        return size;
    }
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<bool>> visited(row,vector<bool>(col,false));
        // 遍历边界岛屿
        int go[4][2] = {0,1,1,0,0,-1,-1,0};
        int x = 0, y = 0;
        for(int i=0; i<4; i++){
            int movex = go[i][0];
            int movey = go[i][1];
            while(1){
                if(!visited[x][y] && grid[x][y]==1){
                    bfs(grid,visited,x,y);
                }
                if(x+movex<0 || x+movex>=row || y+movey<0 || y+movey>=col){
                    break;
                }else{
                    x+=movex;
                    y+=movey;
                }
            }
        }
        // 数飞地数量
        int cnt = 0;
        for(int i=1; i<row-1; i++){
            for(int j=1; j<col-1; j++){
                if(grid[i][j]==1 && !visited[i][j]){
                    cnt+=bfs(grid,visited,i,j);
                }
            }
        }
        return cnt;
    }
};

130.被围绕的区域

130. 被围绕的区域 - 力扣（LeetCode）

和上一道题不同, 这次必须绕边界一周, 标记所有与边界相连的岛屿, 不能像上一道题Java解法那样在bfs()里添加flag用来标记本次搜索是否作数

Java解法

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
class Solution {
    int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    class position{
        int x;
        int y;
        position(int x, int y){this.x=x;this.y=y;};
    }
    int bfs(boolean[][] visited, int[][] grid, int i, int j, int m, int n){
        ArrayDeque<position> q = new ArrayDeque<position>();
        visited[i][j] = true;
        q.addLast(new position(i,j));
        int nextx,nexty;
        int size = 1;
        boolean flag = false;
        while(!q.isEmpty()){
            position p = q.removeFirst();
            for(int k=0; k<4; k++){
                nextx = p.x+dir[k][0];
                nexty = p.y+dir[k][1];
                if(nextx<0 || nextx>=m || nexty<0 || nexty>=n){
                    flag = true;
                    continue;//不能提前退出, 因为必须把这个岛屿的所有格子都标记一下
                }
                if(!visited[nextx][nexty] && grid[nextx][nexty]==1){
                    q.addLast(new position(nextx,nexty));
                    size++;
                    visited[nextx][nexty] = true;
                }
            }
        }
        return flag?0:size;
    }
    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int cnt = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!visited[i][j] && grid[i][j]==1){
                    cnt += bfs(visited,grid,i,j,m,n);
                }
            }
        }
        return cnt;
    }
}

C++解法

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
52
53
54
55
56
57
58
59
60
61
62
class Solution {
private:
    int dir[4][2] = {-1,0,1,0,0,-1,0,1};
    int bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j){
        int size = 1;
        visited[i][j] = true;
        queue<pair<int,int>> q;
        q.push({i,j});
        while(!q.empty()){
            pair<int, int> cur = q.front();
            q.pop();
            int x = cur.first;
            int y = cur.second;
            for(int di=0; di<4; di++){
                int nextx = x + dir[di][0];
                int nexty = y + dir[di][1];
                if(nextx<0 || nextx>=grid.size() || nexty<0 || nexty>=grid[0].size())
                    continue;
                if(grid[nextx][nexty]==1 && !visited[nextx][nexty]){
                    q.push({nextx,nexty});
                    size++;
                    visited[nextx][nexty] = true;
                }
            }
        }
        return size;
    }
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<bool>> visited(row,vector<bool>(col,false));
        // 遍历边界岛屿
        int go[4][2] = {0,1,1,0,0,-1,-1,0};
        int x = 0, y = 0;
        for(int i=0; i<4; i++){
            int movex = go[i][0];
            int movey = go[i][1];
            while(1){
                if(!visited[x][y] && grid[x][y]==1){
                    bfs(grid,visited,x,y);
                }
                if(x+movex<0 || x+movex>=row || y+movey<0 || y+movey>=col){
                    break;
                }else{
                    x+=movex;
                    y+=movey;
                }
            }
        }
        // 数飞地数量
        int cnt = 0;
        for(int i=1; i<row-1; i++){
            for(int j=1; j<col-1; j++){
                if(grid[i][j]==1 && !visited[i][j]){
                    cnt+=bfs(grid,visited,i,j);
                }
            }
        }
        return cnt;
    }
};

463.岛屿的周长

463. 岛屿的周长 - 力扣（LeetCode）

广度优先搜索解法(java)

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
class Solution {
    class po{
        int x;
        int y;
        po(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    int bfs(int[][] grid, boolean[][] visited, int x, int y, int m, int n){
        ArrayDeque<po> q = new ArrayDeque<po>();
        int C = 0;
        q.addLast(new po(x,y));
        visited[x][y] = true;
        while(!q.isEmpty()){
            po p = q.removeFirst();
            // 查看能贡献多少周长
            int nextx,nexty;
            for(int i=0; i<4; i++){
                nextx = p.x+dir[i][0];
                nexty = p.y+dir[i][1];
                if(nextx<0 || nextx==m || nexty<0 || nexty==n){
                    C++;
                }else if(grid[nextx][nexty]==0){
                    C++;
                }else if(!visited[nextx][nexty]){
                    visited[nextx][nexty] = true;
                    q.addLast(new po(nextx,nexty));
                }
            }
        }
        return C;
    }
    public int islandPerimeter(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==1){
                    return bfs(grid,visited,i,j,m,n);
                }
            }
        }
        return 0;
    }
}

虽然这道题被放在了广度优先搜索这篇文章内, 但是思考一下, 每一个方块都可以贡献n个周长(1<=n<=4), 只需要对每个方块的四周探测一遍即可
(java)

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
class Solution {
    public int islandPerimeter(int[][] grid) {
        int ans = 0;
        int m = grid.length;
        int n = grid[0].length;
        int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
        int nextx,nexty;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==0){
                    continue;
                }
                int t = 0;
                for(int k=0; k<4; k++){
                    nextx = i+dir[k][0];
                    nexty = j+dir[k][1];
                    if(nextx<0 || nextx==m || nexty<0 || nexty==n || grid[nextx][nexty]==0){
                        t++;
                    }
                }
                ans+=t;
            }
        }
        return ans;
    }
}

841.钥匙和房间

841. 钥匙和房间 - 力扣（LeetCode）

这道题有多种解法, 当从广度优先搜索的角度探究时, 我们发现, 可以使用一个队列, 拥有一个房间的钥匙时, 就放入队列, 同时做一个布尔型数组, 标记已经有钥匙的房间, 防止重复获取钥匙

每次从队列头获取一个钥匙(没到过的房间), 进入这个房间, 并拿一下所有还没到过房间的钥匙

每次获得一个新的没到过房间的钥匙, 就把这个钥匙放入队列末尾

如果队列为空, 说明无法获取新的钥匙, 此时有两种情况, 所有的房间都被标记过, 所以没有新的钥匙入队, 还有另一种情况, 题目中给的钥匙情况, 已经无法增加新的没到过房间的钥匙, 所以为了方便的判断究竟是哪种情况, 设置一个变量open, 每次新增一个没到过房间的钥匙的时候, open++, 最后如果num==open那么所有房间都可以到达, 如果num!=open说明有的房间不可以到达

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        ArrayDeque<Integer> q = new ArrayDeque<Integer>();
        q.addLast(0);
        int n = rooms.size();
        boolean[] mark = new boolean[n];
        mark[0] = true;
        int open = 1;
        while(!q.isEmpty()){
            Integer i = q.removeFirst();
            List t = rooms.get(i);
            int s = t.size();
            for(int j=0; j<s; j++){
                int tmp = (int)t.get(j);
                if(!mark[tmp]){
                    open++;
                    mark[tmp] = true;
                    q.addLast(tmp);
                }
            }
        }
        return n==open;
    }
}
技术笔记
#Java #算法 #数据结构 #C++ #力扣刷题
广度优先搜索(使用Java和C++实现)
http://example.com/图论广度优先搜索/
作者
李小基
许可协议