Force buckle 1020 Number of enclaves

How small is Russia , Why is NATO afraid ？

It turns out that this is an enclave of Russia . Not all Russian territory .

Give you a size of m x n The binary matrix of grid , among 0 Represents an ocean cell 、1 Represents a land cell .

once Move It refers to walking from one land cell to another （ On 、 Next 、 Left 、 Right ） Land cells or across grid The boundary of the .

Return to grid unable The number of land cells that leave the grid boundary in any number of moves .

  This is a routine bfs Search questions , It is obvious to start with four boundaries ,grid【】【】 by 1 Join the team , Then I use guangsearch , If the value of the lattice connected to the boundary is 1, Just put grid Change it to 0, Then traverse , Look, how many are there 1.

class Solution {
public:
    int room[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

    int numEnclaves(vector<vector<int>>& grid) {
        int x = grid.size(), y = grid[0].size();
        if (x == 1)return 0;
        queue<pair<int, int>>q;
        for (int i = 0; i < y; i++)// Join the team around the border 1
            if (grid[0][i] == 1) 
                q.emplace(0, i);
        for (int i = 0; i < y; i++)
            if (grid[x - 1][i] == 1) 
                q.emplace(x-1, i);
        for (int i = 0; i < x; i++)
            if (grid[i][y-1] == 1) 
                q.emplace(i, y-1);
        for (int i = 0; i < x; i++)
            if (grid[i][0] == 1) 
                q.emplace(i, 0);
        while (!q.empty()) {//bfs Search element 
            int first_x = q.front().first;
            int first_y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {//first Search around elements 
                int next_x = first_x + room[i][0];
                int next_y = first_y + room[i][1];
                if (next_x >= 0 && next_x < x && next_y >= 0 && next_y < y && grid[next_x][next_y] == 1) {
                    q.emplace(next_x, next_y);
                    grid[next_x][next_y] = 0;
			    }
            }
        }
        int k = 0;
        for (int i = 1; i < x-1; i++)
            for (int j = 1; j < y-1; j++)
                if (grid[i][j] == 1)
                    k++;
        return k;
    }
};

I also wrote a lot bfs and dfs It's the topic of , Summarize the idea of this kind of chart topic ：

1. Specify what to use ,bfs still dfs;

2. The first point we want to search （ The starting point ） What is it? ;

3. How can we judge whether we have searched this point ;

4. The answer is given according to the question .

jsl