Dada una array de tamaño N * M y Q consultas, la tarea es encontrar cuántas regiones diferentes habrá allí, después de realizar las consultas. En cada consulta:
- Hay cuatro números enteros x1, y1, x2, y2 que denotan dos celdas de la array (x1, y1) y (x2, y2) que son adyacentes entre sí.
- Cree un límite a lo largo del lado común de las celdas.
Nota: dos regiones son diferentes si no hay manera de una región a otra sin cruzar el límite
Ejemplos:
Entrada: N = 2, M = 2, Q = 2, consultas = { {1, 1, 2, 1}, {2, 2, 1, 2} }
Salida: 2
Explicación:
Ejemplo 1
Vea la imagen de arriba para una mejor comprensión. La figura 1 muestra la array sin ningún límite
. La figura 2 muestra la array después de que se forman los límites entre (1, 1), (2, 1) y (2, 2), (1, 2).
Se crean dos regiones.Entrada: N = 2, M = 2, Q = 10,
consultas = {{2, 1, 2, 2}, {1, 2, 2, 2}, {1, 3, 2, 3}, {1, 4, 2, 4}, {2, 3, 3, 3}, {3, 3, 3, 4}, {3, 3, 4, 3}, {3, 3, 3, 2}, {3, 1, 3, 2}, {4, 1, 4, 2}}Salida: 2
Explicación: vea las regiones formadas en la imagen proporcionada a continuación
Ejemplo 2
Enfoque: el problema se puede resolver utilizando hashing y DFS según la siguiente idea:
Cree hash para almacenar si los límites se forman vertical u horizontalmente y qué celdas ya han tomado parte en las operaciones de formación de límites.
Luego visite las celdas de la array usando dfs y verifique que los límites entre ellos formen una región diferente o no.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Cree dos tablas hash para almacenar el estado de las líneas presentes en celdas adyacentes vertical y horizontalmente.
- Cree otra tabla hash para almacenar si se visita una celda o no.
- Comience a recorrer las consultas, y en cada iteración:
- Compruebe si las dos celdas dadas son adyacentes vertical u horizontalmente.
- Marque las tablas hash de acuerdo con eso para evitar considerarlas en la misma región.
- Atraviesa la array, y en cada iteración:
- Compruebe si la celda actual es visitada o no.
- Si no se visita, incremente el conteo de TotalRegion y luego use DFS para visitar recursivamente sus celdas adyacentes (si no hay límite entre ellas) y marque todas las celdas en esa región como visitadas.
- Devuelve el recuento de TotalRegion en la array después de realizar
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Recursive function to traverse the matrix
void traverse(int i, int j, int N, int M,
vector<vector<bool> >& vis,
vector<vector<bool> >& row,
vector<vector<bool> >& col)
{
if (i <= 0 || i > N || j <= 0 || j > M || vis[i][j])
return;
// Mark Current cell visited.
vis[i][j] = true;
// Traverse adjacent cells in all directions
// (up, down, right, left) that
// do not include lines between
if (row[i][j])
traverse(i, j + 1, N, M,
vis, row, col);
if (col[i][j])
traverse(i + 1, j, N, M,
vis, row, col);
if (row[i][j - 1])
traverse(i, j - 1, N, M,
vis, row, col);
if (col[i - 1][j])
traverse(i - 1, j, N, M,
vis, row, col);
}
// Function to count the total regions
int count(int N, int M, int K,
vector<vector<int> >& q)
{
vector<vector<bool> > row(N + 1,
vector<bool>(
M + 1, true));
vector<vector<bool> > col(N + 1,
vector<bool>(
M + 1, true));
vector<vector<bool> > vis(N + 1,
vector<bool>(
M + 1, false));
for (int i = 0; i < K; i++) {
// Hash array value set to false
// if there is line between
// two adjacent cell in same row
// If query is {0 1 1 1} or
// {1 1 0 1} we make row[0][1]= false,
// that means there is vertical line
// after the cell [0][1]
if (q[i][0] == q[i][2]) {
int mn = min(q[i][1], q[i][3]);
row[q[i][0]][mn] = false;
}
// Hash array value set to false if
// there is line between
// two adjacent cell in same column
// If query is {2 3 2 4} or {2 4 2 3}
// we make col[2][3]= false,
// that means there is horizontal line
// below the cell [2][3]
else {
int mn = min(q[i][0], q[i][2]);
col[mn][q[i][1]] = false;
}
}
// Store count of total regions after
// performing K queries.
int TotalRegion = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
// If current Cell
// is not visited
// then increment the TotalRegion
// count and traverse
// all the cell in that region
if (!vis[i][j]) {
TotalRegion++;
traverse(i, j, N, M,
vis, row, col);
}
}
}
return TotalRegion;
}
// Driver code
int main()
{
vector<vector<int> > q;
int N = 5, M = 5;
int K = 10;
q.push_back({ 2, 1, 2, 2 });
q.push_back({ 1, 2, 2, 2 });
q.push_back({ 1, 3, 2, 3 });
q.push_back({ 1, 4, 2, 4 });
q.push_back({ 2, 3, 3, 3 });
q.push_back({ 3, 3, 3, 4 });
q.push_back({ 3, 3, 4, 3 });
q.push_back({ 3, 3, 3, 2 });
q.push_back({ 3, 1, 3, 2 });
q.push_back({ 4, 1, 4, 2 });
cout << count(N, M, K, q);
return 0;
}
Java
// Java program for above approach
import java.io.*;
import java.util.*;
import java.util.ArrayList;
class GFG {
// Recursive function to traverse the matrix
static void traverse(int i, int j, int N, int M,
boolean[][] vis,
boolean[][] row,
boolean[][] col)
{
if (i <= 0 || i > N || j <= 0 || j > M || vis[i][j])
return;
// Mark Current cell visited.
vis[i][j] = true;
// Traverse adjacent cells in all directions
// (up, down, right, left) that
// do not include lines between
if (row[i][j])
traverse(i, j + 1, N, M,
vis, row, col);
if (col[i][j])
traverse(i + 1, j, N, M,
vis, row, col);
if (row[i][j - 1])
traverse(i, j - 1, N, M,
vis, row, col);
if (col[i - 1][j])
traverse(i - 1, j, N, M,
vis, row, col);
}
// Function to count the total regions
static int count(int N, int M, int K, ArrayList<ArrayList<Integer> > q)
{
boolean[][] row = new boolean[N+1][M+1];
boolean[][] col = new boolean[N+1][M+1];
boolean[][] vis = new boolean[N+1][M+1];
for(int i = 0; i < N+1; i++){
for(int j = 0; j < M+1; j++)
{
row[i][j]=true;
col[i][j]=true;
vis[i][j]=false;
}
}
for (int i = 0; i < K; i++) {
// Hash array value set to false
// if there is line between
// two adjacent cell in same row
// If query is {0 1 1 1} or
// {1 1 0 1} we make row[0][1]= false,
// that means there is vertical line
// after the cell [0][1]
if (q.get(i).get(0) == q.get(i).get(2)) {
int mn = Math.min(q.get(i).get(1), q.get(i).get(3));
row[q.get(i).get(0)][mn] = false;
}
// Hash array value set to false if
// there is line between
// two adjacent cell in same column
// If query is {2 3 2 4} or {2 4 2 3}
// we make col[2][3]= false,
// that means there is horizontal line
// below the cell [2][3]
else {
int mn = Math.min(q.get(i).get(0), q.get(i).get(2));
col[mn][q.get(i).get(1)] = false;
}
}
// Store count of total regions after
// performing K queries.
int TotalRegion = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
// If current Cell
// is not visited
// then increment the TotalRegion
// count and traverse
// all the cell in that region
if (!vis[i][j]) {
TotalRegion++;
traverse(i, j, N, M,
vis, row, col);
}
}
}
return TotalRegion;
}
// driver code
public static void main(String[] args)
{
ArrayList<ArrayList<Integer> > q
= new ArrayList<ArrayList<Integer> >();
int N = 5, M = 5;
int K = 10;
q.add(new ArrayList<Integer>(Arrays.asList(2, 1, 2, 2)));
q.add(new ArrayList<Integer>(Arrays.asList(1, 2, 2, 2)));
q.add(new ArrayList<Integer>(Arrays.asList(1, 3, 2, 3)));
q.add(new ArrayList<Integer>(Arrays.asList(1, 4, 2, 4)));
q.add(new ArrayList<Integer>(Arrays.asList(2, 3, 3, 3)));
q.add(new ArrayList<Integer>(Arrays.asList(3, 3, 3, 4)));
q.add(new ArrayList<Integer>(Arrays.asList(3, 3, 4, 3)));
q.add(new ArrayList<Integer>(Arrays.asList(3, 3, 3, 2)));
q.add(new ArrayList<Integer>(Arrays.asList(3, 1, 3, 2)));
q.add(new ArrayList<Integer>(Arrays.asList(4, 1, 4, 2)));
System.out.print(count(N, M, K, q));
}
}
// This code is contributed by Pushpesh Raj
Python3
# Python code to implement the approach
# Recursive function to traverse the matrix
def traverse(i, j, N, M, vis, row, col):
if (i <= 0 or i > N or j <= 0 or j > M or vis[i][j]):
return
# Mark Current cell visited.
vis[i][j] = True
# Traverse adjacent cells in all directions
# (up, down, right, left) that
# do not include lines between
if (row[i][j]):
traverse(i, j + 1, N, M,vis, row, col)
if (col[i][j]):
traverse(i + 1, j, N, M,vis, row, col)
if (row[i][j - 1]):
traverse(i, j - 1, N, M,vis, row, col)
if (col[i - 1][j]):
traverse(i - 1, j, N, M,vis, row, col)
# Function to count the total regions
def count(N, M, K, q):
row = [[True for col in range(M+1)]for row in range(N+1)]
col = [[True for col in range(M+1)]for row in range(N+1)]
vis = [[False for col in range(M+1)]for row in range(N+1)]
for i in range(K):
# Hash array value set to false
# if there is line between
# two adjacent cell in same row
# If query is {0 1 1 1} or
# {1 1 0 1} we make row[0][1]= false,
# that means there is vertical line
# after the cell [0][1]
if (q[i][0] == q[i][2]):
mn = min(q[i][1], q[i][3])
row[q[i][0]][mn] = False
# Hash array value set to false if
# there is line between
# two adjacent cell in same column
# If query is {2 3 2 4} or {2 4 2 3}
# we make col[2][3]= false,
# that means there is horizontal line
# below the cell [2][3]
else:
mn = min(q[i][0], q[i][2])
col[mn][q[i][1]] = False
# Store count of total regions after
# performing K queries.
TotalRegion = 0
for i in range(1,N+1):
for j in range(1,M+1):
# If current Cell
# is not visited
# then increment the TotalRegion
# count and traverse
# all the cell in that region
if (vis[i][j] == False):
TotalRegion += 1
traverse(i, j, N, M,vis, row, col)
return TotalRegion
# Driver code
q = []
N = 5
M = 5
K = 10
q.append([2, 1, 2, 2])
q.append([1, 2, 2, 2])
q.append([1, 3, 2, 3])
q.append([1, 4, 2, 4])
q.append([2, 3, 3, 3])
q.append([3, 3, 3, 4])
q.append([3, 3, 4, 3])
q.append([3, 3, 3, 2])
q.append([3, 1, 3, 2])
q.append([4, 1, 4, 2])
print(count(N, M, K, q))
# This code is contributed by ShinjanPatra
C#
// C# program for above approach
using System;
public class GFG
{
// Recursive function to traverse the matrix
static void traverse(int i, int j, int N, int M,
bool[, ] vis, bool[, ] row,
bool[, ] col)
{
if (i <= 0 || i > N || j <= 0 || j > M || vis[i, j])
return;
// Mark Current cell visited.
vis[i, j] = true;
// Traverse adjacent cells in all directions
// (up, down, right, left) that
// do not include lines between
if (row[i, j])
traverse(i, j + 1, N, M, vis, row, col);
if (col[i, j])
traverse(i + 1, j, N, M, vis, row, col);
if (row[i, j - 1])
traverse(i, j - 1, N, M, vis, row, col);
if (col[i - 1, j])
traverse(i - 1, j, N, M, vis, row, col);
}
// Function to count the total regions
static int count(int N, int M, int K, int[, ] q)
{
bool[, ] row = new bool[N + 1, M + 1];
bool[, ] col = new bool[N + 1, M + 1];
bool[, ] vis = new bool[N + 1, M + 1];
for (int i = 0; i < N + 1; i++) {
for (int j = 0; j < M + 1; j++) {
row[i, j] = true;
col[i, j] = true;
vis[i, j] = false;
}
}
for (int i = 0; i < K; i++)
{
// Hash array value set to false
// if there is line between
// two adjacent cell in same row
// If query is {0 1 1 1} or
// {1 1 0 1} we make row[0][1]= false,
// that means there is vertical line
// after the cell [0][1]
if (q[i, 0] == q[i, 2]) {
int mn = Math.Min(q[i, 1], q[i, 3]);
row[q[i, 0], mn] = false;
}
// Hash array value set to false if
// there is line between
// two adjacent cell in same column
// If query is {2 3 2 4} or {2 4 2 3}
// we make col[2][3]= false,
// that means there is horizontal line
// below the cell [2][3]
else {
int mn = Math.Min(q[i, 0], q[i, 2]);
col[mn, q[i, 1]] = false;
}
}
// Store count of total regions after
// performing K queries.
int TotalRegion = 0;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
// If current Cell
// is not visited
// then increment the TotalRegion
// count and traverse
// all the cell in that region
if (!vis[i, j]) {
TotalRegion++;
traverse(i, j, N, M, vis, row, col);
}
}
}
return TotalRegion;
}
// Driver Code
public static void Main(string[] args)
{
int[, ] q = { { 2, 1, 2, 2 }, { 1, 2, 2, 2 },
{ 1, 3, 2, 3 }, { 1, 4, 2, 4 },
{ 2, 3, 3, 3 }, { 3, 3, 3, 4 },
{ 3, 3, 4, 3 }, { 3, 3, 3, 2 },
{ 3, 1, 3, 2 }, { 4, 1, 4, 2 } };
int N = 5, M = 5;
int K = 10;
Console.WriteLine(count(N, M, K, q));
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript code to implement the approach
// Recursive function to traverse the matrix
const traverse = (i, j, N, M, vis, row, col) => {
if (i <= 0 || i > N || j <= 0 || j > M || vis[i][j])
return;
// Mark Current cell visited.
vis[i][j] = true;
// Traverse adjacent cells in all directions
// (up, down, right, left) that
// do not include lines between
if (row[i][j])
traverse(i, j + 1, N, M,
vis, row, col);
if (col[i][j])
traverse(i + 1, j, N, M,
vis, row, col);
if (row[i][j - 1])
traverse(i, j - 1, N, M,
vis, row, col);
if (col[i - 1][j])
traverse(i - 1, j, N, M,
vis, row, col);
}
// Function to count the total regions
const count = (N, M, K, q) => {
let row = new Array(N + 1).fill(1).map(() => new Array(M + 1).fill(1));
let col = new Array(N + 1).fill(1).map(() => new Array(M + 1).fill(1));
let vis = new Array(N + 1).fill(0).map(() => new Array(M + 1).fill(0));
for (let i = 0; i < K; i++)
{
// Hash array value set to false
// if there is line between
// two adjacent cell in same row
// If query is {0 1 1 1} or
// {1 1 0 1} we make row[0][1]= false,
// that means there is vertical line
// after the cell [0][1]
if (q[i][0] == q[i][2]) {
let mn = Math.min(q[i][1], q[i][3]);
row[q[i][0]][mn] = false;
}
// Hash array value set to false if
// there is line between
// two adjacent cell in same column
// If query is {2 3 2 4} or {2 4 2 3}
// we make col[2][3]= false,
// that means there is horizontal line
// below the cell [2][3]
else {
let mn = Math.min(q[i][0], q[i][2]);
col[mn][q[i][1]] = false;
}
}
// Store count of total regions after
// performing K queries.
let TotalRegion = 0;
for (let i = 1; i <= N; i++)
{
for (let j = 1; j <= M; j++)
{
// If current Cell
// is not visited
// then increment the TotalRegion
// count and traverse
// all the cell in that region
if (!vis[i][j]) {
TotalRegion++;
traverse(i, j, N, M,
vis, row, col);
}
}
}
return TotalRegion;
}
// Driver code
let q = [];
let N = 5, M = 5;
let K = 10;
q.push([2, 1, 2, 2]);
q.push([1, 2, 2, 2]);
q.push([1, 3, 2, 3]);
q.push([1, 4, 2, 4]);
q.push([2, 3, 3, 3]);
q.push([3, 3, 3, 4]);
q.push([3, 3, 4, 3]);
q.push([3, 3, 3, 2]);
q.push([3, 1, 3, 2]);
q.push([4, 1, 4, 2]);
document.write(count(N, M, K, q));
// This code is contributed by rakeshsahni
</script>
Producción
2
Complejidad de Tiempo: O( N*M + Q )
Espacio Auxiliar: O( N*M )
Publicación traducida automáticamente
Artículo escrito por khatriharsh281 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA