当前位置:网站首页>[graph theory brush question-4] force deduction 778 Swimming in a rising pool
[graph theory brush question-4] force deduction 778 Swimming in a rising pool
2022-04-23 20:17:00 【smile-yan】
Graph theory brush questions
778. Swimming in a rising pool
Try to catch up with the original question Address
Difficulty and label
It's difficult
- Depth-first traversal
- Breadth first traversal
- And find
Title Description
In a n x n
The integer matrix of grid
in , The value of each square grid[i][j]
Indicate location (i, j)
The height of the platform .
When it began to rain , In time for t
when , The water level in the pool is t
. You can swim from one platform to any nearby platform , But the premise is that the water level must submerge both platforms at the same time . Suppose you can move an infinite distance in an instant , That is to say, it is not time-consuming to swim inside the grid by default . Of course , You have to stay in the grid when you swim .
You go from the top left platform of the grid (0,0)
set out . return You reach the lower right platform of the coordinate grid (n-1, n-1)
Minimum time required .
Example 1:
Input : grid = [[0,2],[1,3]]
Output : 3
explain :
Time is 0 when , Your position in the grid is (0, 0).
You can't swim in any direction at this time , Because the heights of platforms in four adjacent directions are greater than the current time of 0 The water level at the end of the day .
Wait for the time to arrive 3 when , You can swim to the platform (1, 1). Because the water level is 3, The platform in the coordinate grid has no comparison with the water level 3 Higher , So you can swim anywhere in the grid
Example 2:
Input : grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output : 16
explain : The final route is marked in bold .
We have to wait for time for 16, Only at this time can the platform be guaranteed (0, 0) and (4, 4) It's connected
Tips :
n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n^2
grid[i][j] Each value in No duplication
Topic analysis
The topic is very interesting , But it's really hard . First of all, a simple understanding of the scene can assume that we are a duck , From you to [0, 0]
Swim home [n-1, n-1]
. Note that swim
get home , Therefore, the water must exceed the high platform to show that this road is accessible , Otherwise, the water is lower than the platform and you can't swim there .
Now combine the diagram 1, Be sure to wait until the water level reaches 3 Before you can pass .
Then we give the important conclusion of our reading topic :
- hypothesis
W = Max(grid)
, namely W Is the largest number of two-dimensional arrays , When the water level reachesW
There must be a way , The lovely duckling will be able to go home . - Our answer must be
[0, W]
Between .
So this topic turns to finding a threshold threshold
∈ [ 0 , W ] \in [0, W] ∈[0,W] , bring , When the water level reaches threshold
when , You can get at least one from [0, 0]
To [n-1, n-1]
The way home .
We have a two-dimensional array ary
, Size is n x n
, All defaults to 0.
Steps are as follows :
- Suppose the threshold is
Q
, For a two-dimensional arrayary
The position where the assignment is performed , The specific rules are :If grid[i][j] <= threshold Q, be ary[i][j] = 1, It means that this point can pass .
- Traverse ary, Find out if there is a path
[0, 0]
To[n-1, n-1]
.
Obviously , If Q
The bigger it is , The more points you can pass .
Code implementation 1—— DFS + Binary query
- initialization
visited
Array ,visited[i][j]
bytrue
Indicates that you have accessed or cannot access . - Write a DFS function , Traverse all paths . If you can reach your destination ( get home ) Just go back to true;
- Binary search threshold , Initialize each time according to the threshold visited Array , And then call DFS Function to check whether you can access .
Important supplement
:grid[0][0]
The location is not necessarily 0
, So the output is target
Must be greater than or equal to grid[0][0]
, Therefore, the starting point of binary search is grid[0][0]
, According to the subject conditions, the maximum value is also less than n*n
, So the end point of binary search is n*n-1
.
class Solution {
public:
const int dx[4] = {
0, 1, 0, -1};
const int dy[4] = {
1, 0, -1, 0};
/** * initialization visited Array , Place the unqualified points in true */
void initVisited(vector<vector<int>> grid,
vector<vector<bool>>& visited,
int threshold) {
int n = grid.size();
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
visited[i][j] = grid[i][j] > threshold;
}
}
}
/** * dfs Traverse */
bool dfs(vector<vector<bool>>& visited,
int x, int y) {
int n = visited.size();
// 1. Judge whether the destination is reached
if (x == n-1 && y == n-1) {
return true;
}
// 2. Tag has been accessed
visited[x][y] = true;
// 3. Depth-first traversal
for (int i=0; i<4; i++) {
int mx = x + dx[i];
int my = y + dy[i];
if (mx >= 0 && mx < n && my >= 0 && my < n && !visited[mx][my] ) {
// If you reach the end return otherwise continue for loop
if (dfs(visited, mx, my)) {
return true;
}
}
}
return false;
}
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
int left = grid[0][0];
int right = n*n-1;
vector<vector<bool>> visited(n, vector<bool>(n));
while (left < right) {
int mid = (left+right)/2;
initVisited(grid, visited, mid);
if (dfs(visited, 0, 0)) {
right = mid;
} else {
left = mid+1;
}
}
// left == right
return left;
}
};
- Time complexity : O ( N 2 log N ) O(N^2 \log N) O(N2logN)
- Spatial complexity : O ( N 2 ) O(N^2) O(N2)
Additional explanation : If the topic does not emphasize the value range of each point , Then you can first find the largest and smallest , Then make a binary query , Same effect , Does not affect the overall time .
in addition , This problem is not the shortest path problem , The concern is how much water the ducklings can pass through , therefore , Even if there may be many paths in the end , We just need to make sure we have one that we can go with .
summary
It is basically the same as the official explanation , But the algorithm 1 My idea is to attach additional conditions to visited
Array , dfs Basically nothing has changed .
If you understand the meaning of this topic , The only error prone thing should be Dichotomy search threshold . In fact, I passed all the test cases first and prompted to timeout , After reading the official source code, I remembered to find it by dichotomy .
In a word, it is an interesting topic , Never be difficult
Two words bluff .
Smileyan
2022.3.22 17:08
版权声明
本文为[smile-yan]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204210553133212.html
边栏推荐
- R语言使用timeROC包计算无竞争风险情况下的生存资料多时间AUC值、使用confint函数计算无竞争风险情况下的生存资料多时间AUC指标的置信区间值
- Five minutes to show you what JWT is
- Error reported by Azkaban: Azkaban jobExecutor. utils. process. ProcessFailureException: Process exited with code 64
- NC basic usage
- AQS learning
- MySQL 进阶 锁 -- MySQL锁概述、MySQL锁的分类:全局锁(数据备份)、表级锁(表共享读锁、表独占写锁、元数据锁、意向锁)、行级锁(行锁、间隙锁、临键锁)
- How about Bohai futures. Is it safe to open futures accounts?
- Servlet learning notes
- Project training of Software College of Shandong University - Innovation Training - network security shooting range experimental platform (VII)
- Remote code execution in Win 11 using wpad / PAC and JScript
猜你喜欢
Azkaban recompile, solve: could not connect to SMTP host: SMTP 163.com, port: 465 [January 10, 2022]
Livego + ffmpeg + RTMP + flvjs to realize live video
Building googlenet neural network based on pytorch for flower recognition
Sqoop imports tinyint type fields to boolean type
How to protect ECs from hacker attacks?
Compact CUDA tutorial - CUDA driver API
[talkative cloud native] load balancing - the passenger flow of small restaurants has increased
SQL Server Connectors By Thread Pool | DTSQLServerTP plugin instructions
SQL Server Connectors By Thread Pool | DTSQLServerTP plugin instructions
SIGIR'22 "Microsoft" CTR estimation: using context information to promote feature representation learning
随机推荐
Handwritten Google's first generation distributed computing framework MapReduce
Leetcode XOR operation
Openharmony open source developer growth plan, looking for new open source forces that change the world!
STM32 Basics
【文本分类案例】(4) RNN、LSTM 电影评价倾向分类,附TensorFlow完整代码
R语言使用caret包的preProcess函数进行数据预处理:对所有的数据列进行BoxCox变换处理(将非正态分布数据列转换为正态分布数据、不可以处理负数)、设置method参数为BoxCox
CVPR 2022 | QueryDet:使用级联稀疏query加速高分辨率下的小目标检测
DNS cloud school | quickly locate DNS resolution exceptions and keep these four DNS status codes in mind
DNS cloud school rising posture! Three advanced uses of authoritative DNS
Introduction to link database function of cadence OrCAD capture CIS replacement components, graphic tutorial and video demonstration
Electron入门教程4 —— 切换应用的主题
nc基础用法2
山东大学软件学院项目实训-创新实训-网络安全靶场实验平台(八)
Azkaban recompile, solve: could not connect to SMTP host: SMTP 163.com, port: 465 [January 10, 2022]
山东大学软件学院项目实训-创新实训-网络安全靶场实验平台(五)
Project training of Software College of Shandong University - Innovation Training - network security shooting range experimental platform (V)
Leetcode dynamic planning training camp (1-5 days)
R language uses econocrats package to create microeconomic or macroeconomic map, visualize indifference function indifference curve, customize calculation intersection, and customize the parameters of
WordPress plug-in: WP CHINA Yes solution to slow domestic access to the official website
Electron入门教程3 ——进程通信