当前位置:网站首页>Force buckle 1020 Number of enclaves
Force buckle 1020 Number of enclaves
2022-07-06 01:25:00 【zjsru_ Beginner】
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
边栏推荐
- A Cooperative Approach to Particle Swarm Optimization
- 【已解决】如何生成漂亮的静态文档说明页
- Ubantu check cudnn and CUDA versions
- 有谁知道 达梦数据库表的列的数据类型 精度怎么修改呀
- WGet: command line download tool
- Alibaba-Canal使用详解(排坑版)_MySQL与ES数据同步
- How to extract MP3 audio from MP4 video files?
- Loop structure of program (for loop)
- SPIR-V初窺
- [understanding of opportunity-39]: Guiguzi - Chapter 5 flying clamp - warning 2: there are six types of praise. Be careful to enjoy praise as fish enjoy bait.
猜你喜欢
[technology development -28]: overview of information and communication network, new technology forms, high-quality development of information and communication industry
Huawei converged VLAN principle and configuration
[技术发展-28]:信息通信网大全、新的技术形态、信息通信行业高质量发展概览
A Cooperative Approach to Particle Swarm Optimization
Threedposetracker project resolution
Dede collection plug-in free collection release push plug-in
Opinions on softmax function
Finding the nearest common ancestor of binary search tree by recursion
Hcip---ipv6 experiment
Alibaba-Canal使用详解(排坑版)_MySQL与ES数据同步
随机推荐
[the most complete in the whole network] |mysql explain full interpretation
伦敦银走势中的假突破
GNSS terminology
ORA-00030
A picture to understand! Why did the school teach you coding but still not
Differences between standard library functions and operators
A Cooperative Approach to Particle Swarm Optimization
Netease smart enterprises enter the market against the trend, and there is a new possibility for game industrialization
MATLB | real time opportunity constrained decision making and its application in power system
[solved] how to generate a beautiful static document description page
SPIR-V初窺
Four commonly used techniques for anti aliasing
Recommended areas - ways to explore users' future interests
ThreeDPoseTracker项目解析
Unity VR solves the problem that the handle ray keeps flashing after touching the button of the UI
【第30天】给定一个整数 n ,求它的因数之和
A Cooperative Approach to Particle Swarm Optimization
Tcpdump: monitor network traffic
一图看懂!为什么学校教了你Coding但还是不会的原因...
Finding the nearest common ancestor of binary tree by recursion