当前位置:网站首页>Pacific Atlantic current problem
Pacific Atlantic current problem
2022-07-23 14:16:00 【One 829】
There is one with The Pacific Ocean and The Atlantic ocean m x n Bordering rectangular islands . The Pacific Ocean Touch the left and upper edges of the island , The Atlantic ocean Touch the right and lower edges of the island .
The island is divided into square cells . Given a m x n Integer matrix heights, among heights[r][c] Represents the cell at the coordinates Altitude (r, c).
There is a lot of rainfall on the island , If the height of adjacent cells is less than or equal to The height of the current cell , The rain can go straight north 、 south 、 In the east 、 West flow to adjacent cells . Water can flow into the ocean from any cell adjacent to the ocean .
return Grid coordinates Of 2D list result, among Indicates that rainwater can flow from the cell The Pacific Ocean and The Atlantic ocean .result[i] = [ri, ci](ri, ci)
Example 1:

Input : Height = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4, 5],[5,1,1,2,4]] Output : [[0,4],[1,3],[1,4],[2,2],[3,0],[3 ,1],[4,0]] Example 2:
Input : Height = [[2,1],[1,2]] Output : [[0,0],[0,1],[1,0],[1,1]] Error code
#include<iostream>
using namespace std;
int height[201][201], book[201][201];
int m, n,num=1;
// Current point coordinates
void dfs(int x, int y) {
int i, j, k, tx, ty;
// Define four directions
int next[4][2] = {
{0,1},{1,0},{0,-1},{-1,0}
};// Right down left up
// Try whether you can walk in four directions
for (k = 0;k < 4;k++) {
tx = x + next[k][0];
ty = y + next[k][1];
// If the right point is larger than the current point, it can flow through and then judge whether the next point meets the conditions , Find the right book All set
if (tx>=0 && ty>=0 && tx<n && ty<m &&height[tx][ty] >= height[x][y]&&book[tx][ty]==0) {
book[tx][ty] =1;
dfs(tx, ty);
}
}
return;
}
int main() {
int i, j, a[201][201] = { 0 }, b[201][201];
// Enter row and column
cin >> n >> m;
// input data
for (i = 0;i < n;i++)
for (j = 0;j < m;j++)
cin >> height[i][j];
// Points that meet the conditions enter the search ( The surrounding points are divided into four parts )
// On
for (i = 0;i < n;i++) {
book[0][i] = 1;
dfs(0, i);
}
// Left
for (i = 1;i < n;i++){
book[i][0] = 1;
dfs(i, 0);}
for (i = 0;i < n;i++)
for (j = 0;j < m;j++)
a[i][j] = book[i][j];// take book All passed in are assigned to a Array , The staging
// Empty book Tag array
for (i = 0;i < n;i++) {
for (j = 0;j < m;j++)
book[i][j] = { 0 };
}
cout << endl;
// Next
for (i = 1;i < n;i++) {
book[4][i] = 1;
dfs(n-1, i);
}
// Right
for (i = 1;i < n - 1;i++) {
book[i][4] = 1;
dfs(i, n-1);
}
// look for a and book Output the overlapped part of the array
for (i = 0;i < n;i++)
for (j = 0;j < m;j++)
{
if (a[i][j] == book[i][j])
cout << i << " " << j << endl;
}
return 0;
}
5 5
1 2 2 3 5
3 2 3 4 4
2 4 5 3 1
6 7 1 4 5
5 1 1 2 4
边栏推荐
猜你喜欢

Rtx3080 is equivalent to GTX. What kind of graphics card is rtx3080? What level is rtx3080

MySQL enables scheduled task execution

Overlayfs source code parsing

rtx3070ti显卡什么水平 rtx3070ti显卡什么级别 rtx3070ti显卡怎么样

4. 寻找两个正序数组的中位数

采样和数据驱动

Towhee 每周模型

Differences between Xiaomi 12s pro and Xiaomi 12pro Tianji version configuration comparison between the two

200 lines of code, in-depth analysis of the principle and implementation of dynamic calculation diagram

第五天筆記
随机推荐
强化学习——策略梯度理解点
第五天筆記
STM32 output sine wave +cubemx configuration +hal Library
Uiscrollview (uicollectionview) prohibits horizontal and vertical sliding at the same time
达人评测酷睿i7 12850hx和i7 12700h选哪个
OSPF综合实验
OSPF details (1)
链表复习!
rtx3080ti和rtx3080差距 3080和3080ti参数对比
iQOO 10 Pro和vivo X80 Pro区别 哪个好详细参数配置对比
强化學習——策略梯度理解點
LabVIEW运行中改变Chart的历史长度
测试平台、硬件设计描述
动态规划-- 背包问题
第四天笔记
mysql开启定时调度任务执行
-bash: ifconfig: command not found
Fastadmin changes the pop-up size of the default table button
NOTICE: PHP message: PHP Warning: PHP Startup: Unable to load dynamic library ‘*****‘
How about the performance of Intel Celeron 7305? What level is it equivalent to