BFS solution


  • 0
    T
    class Solution {
    public:
        int MOVE[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        int islandPerimeter(vector<vector<int>>& grid) {
            int res = 0;
            int N = grid.size();
            int M = grid[0].size();
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < M; ++j) {
                    if (grid[i][j] == 1) {
                        //BFS
                        queue<pair<int, int> > q;
                        q.push(make_pair(i, j));
                        vector<vector<bool> > vis(N, vector<bool>(M, false));
                        vis[i][j] = true;
                        while (!q.empty()) {
                            pair<int, int> t = q.front(); q.pop();
                            for (int z = 0; z < 4; ++z) {
                                int nx = t.first + MOVE[z][0];
                                int ny = t.second + MOVE[z][1];
                                if (nx < 0 || nx >= N || ny < 0 || ny >= M || grid[nx][ny] == 0) {
                                    res++;
                                    continue;
                                }
                                if (vis[nx][ny]) continue;
                                q.push(make_pair(nx,ny));
                                vis[nx][ny] = 1;
                            }
                        }
                        goto returnres;
                    }
                }
            }
            returnres:
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.