Hay una isla rectangular de N x M que bordea tanto el Océano Pacífico como el Océano Atlántico. El Océano Pacífico toca los bordes izquierdo y superior de la isla, y el Océano Atlántico toca los bordes derecho e inferior de la isla.
La isla está dividida en una cuadrícula de celdas cuadradas. La isla recibe mucha lluvia y el agua de lluvia puede fluir hacia las celdas vecinas directamente al norte, sur, este y oeste si la altura de la celda vecina es menor o igual que la altura de la celda actual. El agua puede fluir desde cualquier celda adyacente a un océano hacia el océano.
Dada una array mat[][] que tiene N filas y M columnas donde mat[x][y] representa la altura sobre el nivel del mar de la celda en la coordenada (x, y) , la tarea es encontrar el número de coordenadas (x , y) de modo que el agua de lluvia pueda fluir desde la celda (x, y) hacia los océanos Pacífico y Atlántico.
Ejemplo:
Entrada: mat[][] = {{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}}Salida: 7
Explicación: En la array dada, hay 7 coordenadas a través de las cuales el agua puede fluir hacia ambos lagos. Ellos son (0, 4), (1, 3), (1, 4), (2, 2), (3, 0), (3, 1) y (4, 0)Entrada: mat[][] = {{2, 2},
{2, 2}}
Salida: 4
Ejemplo: En el siguiente ejemplo, todas las celdas permiten que el agua fluya hacia ambos lagos.
Enfoque: el problema dado se puede resolver utilizando un recorrido DFS o BFS . La idea es marcar todas las celdas a las que se puede acceder desde las celdas conectadas directamente desde los océanos Pacífico y Atlántico por separado utilizando DFS o BFS. El conteo de celdas que están conectadas a través de ambos es la respuesta requerida. A continuación se detallan los pasos a seguir:
- Cree dos colas q1 y q2 para almacenar las coordenadas de la array como un par.
- Atraviese toda la array y almacene las coordenadas conectadas directamente con el Océano Pacífico a q1 y realice un recorrido BFS desde todas las coordenadas en q1 y márquelas como visitadas.
- Del mismo modo, recorra toda la array y almacene las coordenadas conectadas directamente con el Océano Atlántico en q2 y realice un recorrido BFS desde todas las coordenadas en q2 y márquelas como visitadas.
- Recorra la array mat[][] dada y mantenga el recuento de las coordenadas que se visitan durante ambos recorridos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program of the above approach
#include <bits/stdc++.h>
using namespace std;
int x[5] = { 0, 0, -1, 1 };
int y[5] = { 1, -1, 0, 0 };
// Function to check if coordinate
// (i, j) lies inside N x M matrix
bool safe(int i, int j, int N, int M)
{
if (i < 0 || j < 0 || i >= N || j >= M)
return false;
return true;
}
// Function to perform a BFS
// Traversal and mark visited
void BFS(vector<vector<int> > matrix, int N, int M,
queue<pair<int, int> > q,
vector<vector<bool> >& vis)
{
// Loop to traverse q
while (q.empty() == false) {
// Stores current coordinate
pair<int, int> cur = q.front();
q.pop();
// Mark current visited
vis[cur.first][cur.second] = true;
for (int i = 0; i < 4; i++) {
int nx = cur.first + x[i];
int ny = cur.second + y[i];
// If coordinate (nx, ny)
// is inbound and rechable
if (safe(nx, ny, N, M)
&& matrix[nx][ny]
>= matrix[cur.first]
[cur.second]
&& vis[nx][ny] == false) {
// Insert into queue
q.push({ nx, ny });
// Mark visited
vis[nx][ny] = true;
}
}
}
}
// Function to find the count of
// valid coordinates
int countCoordinates(vector<vector<int> > mat,
int N, int M)
{
// Queue to perform BFS
queue<pair<int, int> > q1, q2;
// Stores the visited coordinates
// during the 1st traversal
vector<vector<bool> > visited1(
N,
vector<bool>(M, false));
// Stores the visited coordinates
// during the 2nd traversal
vector<vector<bool> > visited2(
N,
vector<bool>(M, false));
// Insert the coordinates
// directly connected
for (int i = 0; i < M; i++) {
q1.push({ 0, i });
q2.push({ N - 1, i });
}
for (int j = 0; j < N - 1; j++) {
q1.push({ j + 1, 0 });
q2.push({ j, M - 1 });
}
// BFS for the 1st ocean
BFS(mat, N, M, q1, visited1);
// BFS for the 2nd ocean
BFS(mat, N, M, q2, visited2);
// Stores the required count
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// If coordinate (i, j)
// is reachable from both
if (visited1[i][j]
&& visited2[i][j]) {
// Update count
ans++;
}
}
}
// Return Answer
return ans;
}
// Driver code
int main()
{
vector<vector<int> > mat
= { { 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 } };
cout << countCoordinates(mat, mat.size(),
mat[0].size());
return 0;
}
Java
// Java Program of the above approach
import java.util.*;
class GFG{
static int x[] = { 0, 0, -1, 1 };
static int y[] = { 1, -1, 0, 0 };
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to check if coordinate
// (i, j) lies inside N x M matrix
static boolean safe(int i, int j, int N, int M)
{
if (i < 0 || j < 0 || i >= N || j >= M)
return false;
return true;
}
// Function to perform a BFS
// Traversal and mark visited
static void BFS(int[][] matrix, int N, int M,
Queue<pair> q,
boolean [][]vis)
{
// Loop to traverse q
while (q.isEmpty() == false) {
// Stores current coordinate
pair cur = q.peek();
q.remove();
// Mark current visited
vis[cur.first][cur.second] = true;
for (int i = 0; i < 4; i++) {
int nx = cur.first + x[i];
int ny = cur.second + y[i];
// If coordinate (nx, ny)
// is inbound and rechable
if (safe(nx, ny, N, M)
&& matrix[nx][ny]
>= matrix[cur.first]
[cur.second]
&& vis[nx][ny] == false) {
// Insert into queue
q.add(new pair( nx, ny ));
// Mark visited
vis[nx][ny] = true;
}
}
}
}
// Function to find the count of
// valid coordinates
static int countCoordinates(int[][] mat,
int N, int M)
{
// Queue to perform BFS
Queue<pair > q1 =new LinkedList<>();
Queue<pair > q2 =new LinkedList<>();
// Stores the visited coordinates
// during the 1st traversal
boolean visited1[][] = new boolean[N][M];
// Stores the visited coordinates
// during the 2nd traversal
boolean visited2[][] = new boolean[N][M];
// Insert the coordinates
// directly connected
for (int i = 0; i < M; i++) {
q1.add(new pair( 0, i ));
q2.add(new pair( N - 1, i ));
}
for (int j = 0; j < N - 1; j++) {
q1.add(new pair( j + 1, 0 ));
q2.add(new pair( j, M - 1 ));
}
// BFS for the 1st ocean
BFS(mat, N, M, q1, visited1);
// BFS for the 2nd ocean
BFS(mat, N, M, q2, visited2);
// Stores the required count
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// If coordinate (i, j)
// is reachable from both
if (visited1[i][j]
&& visited2[i][j]) {
// Update count
ans++;
}
}
}
// Return Answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int[][] mat
= { { 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 } };
System.out.print(countCoordinates(mat, mat[0].length,
mat[1].length));
}
}
// This code contributed by shikhasingrajput
Python3
Steps = [ [-1,0], # Up [0,1], # Right [1,0], # bottom [0,-1] # Left ] def withinLimits(row_num, col_num, total_rows, total_cols): if 0 <= row_num < total_rows and 0 <= col_num < total_cols: return True return False def waterSlope(oceanMatrix, matrix, row, col): nrows, ncols = len(matrix), len(matrix[0]) for i in Steps: if withinLimits(row+i[0], col+i[1], nrows, ncols): if matrix[row+i[0]][col+i[1]] >= matrix[row][col] and not oceanMatrix[row+i[0]][col+i[1]]: oceanMatrix[row+i[0]][col+i[1]] = True waterSlope(oceanMatrix, matrix, row+i[0], col+i[1]) def commonWaterFlow(matrix): matrix_rows = len(matrix) matrix_cols = len(matrix[0]) pacificMatrix = [[False for _ in range(matrix_cols)] for _ in range(matrix_rows)] atlanticMatrix = [[False for _ in range(matrix_cols)] for _ in range(matrix_rows)] pacificMatrix[0][1] = True pacificMatrix[0][2] = True for i in range(matrix_cols): pacificMatrix[0][i] = True atlanticMatrix[matrix_rows-1][i] = True for i in range(matrix_rows): pacificMatrix[i][0] = True atlanticMatrix[i][matrix_cols-1] = True for i in range(matrix_cols): waterSlope(pacificMatrix, matrix, 0, i) waterSlope(atlanticMatrix, matrix, matrix_rows-1, i) for i in range(matrix_rows): waterSlope(pacificMatrix, matrix, i, 0) waterSlope(atlanticMatrix, matrix, i, matrix_cols-1) Count = 0 for i in range(matrix_rows): for j in range(matrix_cols): if pacificMatrix[i][j] and atlanticMatrix[i][j]: Count += 1 return Count mat = [ [ 1, 2, 2, 3, 5 ], # T-T-T-T-T F-F-F-F-T [ 3, 2, 3, 4, 4 ], # T-T-T-T-T F-F-F-T-T [ 2, 4, 5, 3, 1 ], # T-T-T-F-F F-F-T-T-T [ 6, 7, 1, 4, 5 ], # T-T-F-F-F T-T-T-T-T [ 5, 1, 1, 2, 4 ] ] # T-F-F-F-F T-T-T-T-T print(commonWaterFlow(mat))
C#
// C# Program of the above approach
using System;
using System.Collections.Generic;
public class GFG{
static int []x = { 0, 0, -1, 1 };
static int []y = { 1, -1, 0, 0 };
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to check if coordinate
// (i, j) lies inside N x M matrix
static bool safe(int i, int j, int N, int M)
{
if (i < 0 || j < 0 || i >= N || j >= M)
return false;
return true;
}
// Function to perform a BFS
// Traversal and mark visited
static void BFS(int[,] matrix, int N, int M,
Queue<pair> q,
bool [,]vis)
{
// Loop to traverse q
while (q.Count!=0 ) {
// Stores current coordinate
pair cur = q.Peek();
q.Dequeue();
// Mark current visited
vis[cur.first,cur.second] = true;
for (int i = 0; i < 4; i++) {
int nx = cur.first + x[i];
int ny = cur.second + y[i];
// If coordinate (nx, ny)
// is inbound and rechable
if (safe(nx, ny, N, M)
&& matrix[nx,ny]
>= matrix[cur.first,cur.second]
&& vis[nx,ny] == false) {
// Insert into queue
q.Enqueue(new pair( nx, ny ));
// Mark visited
vis[nx,ny] = true;
}
}
}
}
// Function to find the count of
// valid coordinates
static int countCoordinates(int[,] mat,
int N, int M)
{
// Queue to perform BFS
Queue<pair > q1 =new Queue<pair >();
Queue<pair > q2 =new Queue<pair >();
// Stores the visited coordinates
// during the 1st traversal
bool [,]visited1 = new bool[N,M];
// Stores the visited coordinates
// during the 2nd traversal
bool [,]visited2 = new bool[N,M];
// Insert the coordinates
// directly connected
for (int i = 0; i < M; i++) {
q1.Enqueue(new pair( 0, i ));
q2.Enqueue(new pair( N - 1, i ));
}
for (int j = 0; j < N - 1; j++) {
q1.Enqueue(new pair( j + 1, 0 ));
q2.Enqueue(new pair( j, M - 1 ));
}
// BFS for the 1st ocean
BFS(mat, N, M, q1, visited1);
// BFS for the 2nd ocean
BFS(mat, N, M, q2, visited2);
// Stores the required count
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// If coordinate (i, j)
// is reachable from both
if (visited1[i,j]
&& visited2[i,j]) {
// Update count
ans++;
}
}
}
// Return Answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
int[,] mat
= { { 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 } };
Console.Write(countCoordinates(mat, mat.GetLength(0),
mat.GetLength(1)));
}
}
// This code contributed by shikhasingrajput
Producción
7
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por lalitdungriyal4 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA