Dada una cuadrícula A de tamaño N*M que consta de K celdas indicadas por valores en el rango [1, K] , algunas celdas bloqueadas indicadas por -1 y las restantes celdas desbloqueadas indicadas por 0 , la tarea es verificar si es posible conectarse esas células K, directa o indirectamente, desbloqueando al menos una célula. Es posible moverse solo a las celdas adyacentes horizontales y verticales adyacentes.
Ejemplos
Input:
A = {{0, 5, 6, 0},
{3, -1, -1, 4},
{-1, 2, 1, -1},
{-1, -1, -1, -1}},
K = 6
Output: Yes
Explanation:
Unblocking cell (2, 2) or (2, 3) or (3, 1) or
(3, 4) would make all the K cells connected.
Input:
A = {{-1, -1, 3, -1},
{1, 0, -1, -1},
{-1, -1, -1, 0},
{-1, 0, 2, -1}},
K = 3
Output: No
Explanation:
Atleast two cells need to be unblocked.
Enfoque: Realice BFS desde las celdas numeradas del 1 al K y marque cada celda por el componente al que pertenece. Compruebe si hay alguna celda bloqueada que tenga celdas adyacentes que pertenezcan a diferentes componentes. Si existe alguno, entonces es posible conectarse desbloqueando esa celda. De lo contrario, no es posible.
Ejemplo:
Después de realizar BFS y etiquetar las celdas por su número de componentes, la array aparece de la siguiente manera:
A = {{1, 1, 1, 1}, {1, -1, -1, 1}, {-1, 2, 2, -1}, {-1, -1, -1, -1}}
El número de etiquetas diferentes alrededor de la celda (2, 2) es 2.
Por lo tanto, desbloquearla conectará las K celdas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
#define pairs pair<int, int>
void check(int k, vector<vector<int> > a,
int n, int m)
{
int cells[k][2];
bool visited[n][m];
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] != 0
&& a[i][j] != -1) {
cells[count][0] = i;
cells[count][1] = j;
count++;
}
visited[i][j] = false;
}
}
// Arrays to make grid traversals easier
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
// Store number of components
int component = 0;
// Perform BFS and mark every cell
// by the component in which it belongs
for (int i = 0; i < k; i++) {
int x = cells[i][0], y = cells[i][1];
if (visited[x][y])
continue;
component++;
queue<pairs> cells;
cells.push(make_pair(x, y));
visited[x][y] = true;
while (!cells.empty()) {
pairs z = cells.front();
cells.pop();
a[z.first][z.second] = component;
for (int j = 0; j < 4; j++) {
int new_x = z.first + dx[j];
int new_y = z.second + dy[j];
if (new_x < 0 || new_x >= n
|| new_y < 0 || new_y >= m)
continue;
if (visited[new_x][new_y]
|| a[new_x][new_y] == -1)
continue;
cells.push(make_pair(new_x, new_y));
visited[new_x][new_y] = true;
}
}
}
int maximum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == -1) {
unordered_set<int> set;
for (int kk = 0; kk < 4; kk++) {
int xx = i + dx[kk];
int yy = j + dy[kk];
if (xx < 0 || xx >= n
|| yy < 0 || yy >= m)
continue;
// if the cell doesn't
// belong to any component
if (a[xx][yy] <= 0)
continue;
set.insert(a[xx][yy]);
}
int s = set.size();
maximum = max(s, maximum);
}
}
}
if (maximum == component) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
int main()
{
int k = 6;
int n = 4, m = 4;
vector<vector<int> > a
= { { 0, 5, 6, 0 },
{ 3, -1, -1, 4 },
{ -1, 2, 1, -1 },
{ -1, -1, -1, -1 } };
check(k, a, n, m);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static void check(int k, int [][]a,
int n, int m)
{
int [][]cell = new int[k][2];
boolean [][]visited = new boolean[n][m];
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] != 0
&& a[i][j] != -1) {
cell[count][0] = i;
cell[count][1] = j;
count++;
}
visited[i][j] = false;
}
}
// Arrays to make grid traversals easier
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
// Store number of components
int component = 0;
// Perform BFS and mark every cell
// by the component in which it belongs
for (int i = 0; i < k; i++) {
int x = cell[i][0], y = cell[i][1];
if (visited[x][y])
continue;
component++;
Queue<pair> cells = new LinkedList<>();
cells.add(new pair(x, y));
visited[x][y] = true;
while (!cells.isEmpty()) {
pair z = cells.peek();
cells.remove();
a[z.first][z.second] = component;
for (int j = 0; j < 4; j++) {
int new_x = z.first + dx[j];
int new_y = z.second + dy[j];
if (new_x < 0 || new_x >= n
|| new_y < 0 || new_y >= m)
continue;
if (visited[new_x][new_y]
|| a[new_x][new_y] == -1)
continue;
cells.add(new pair(new_x, new_y));
visited[new_x][new_y] = true;
}
}
}
int maximum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == -1) {
HashSet<Integer> set = new HashSet<Integer>();
for (int kk = 0; kk < 4; kk++) {
int xx = i + dx[kk];
int yy = j + dy[kk];
if (xx < 0 || xx >= n
|| yy < 0 || yy >= m)
continue;
// if the cell doesn't
// belong to any component
if (a[xx][yy] <= 0)
continue;
set.add(a[xx][yy]);
}
int s = set.size();
maximum = Math.max(s, maximum);
}
}
}
if (maximum == component) {
System.out.print("Yes\n");
}
else {
System.out.print("No\n");
}
}
public static void main(String[] args)
{
int k = 6;
int n = 4, m = 4;
int [][]a
= { { 0, 5, 6, 0 },
{ 3, -1, -1, 4 },
{ -1, 2, 1, -1 },
{ -1, -1, -1, -1 } };
check(k, a, n, m);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach
from collections import deque as queue
def check(k, a, n, m):
cells = [[0 for i in range(2)] for i in range(k)]
visited = [[0 for i in range(m)] for i in range(n)]
count = 0
for i in range(n):
for j in range(m):
if (a[i][j] != 0
and a[i][j] != -1):
cells[count][0] = i
cells[count][1] = j
count += 1
visited[i][j] = False
# Arrays to make grid traversals easier
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# Store number of components
component = 0
# Perform BFS and mark every cell
# by the component in which it belongs
for i in range(k):
x = cells[i][0]
y = cells[i][1]
if (visited[x][y]):
continue
component += 1
cell = queue()
cell.append([x, y])
visited[x][y] = True
while (len(cell) > 0):
z = cell.popleft()
a[z[0]][z[1]] = component
for j in range(4):
new_x = z[0] + dx[j]
new_y = z[1] + dy[j]
if (new_x < 0 or new_x >= n
or new_y < 0 or new_y >= m):
continue
if (visited[new_x][new_y]
or a[new_x][new_y] == -1):
continue
cell.append([new_x, new_y])
visited[new_x][new_y] = True
maximum = 0
for i in range(n):
for j in range(m):
if (a[i][j] == -1):
se = dict()
for kk in range(4):
xx = i + dx[kk]
yy = j + dy[kk]
if (xx < 0 or xx >= n
or yy < 0 or yy >= m):
continue
# if the cell doesn't
# belong to any component
if (a[xx][yy] <= 0):
continue
se[a[xx][yy]] = 1
s = len(se)
maximum = max(s, maximum)
if (maximum == component):
print("Yes\n")
else:
print("No\n")
# Driver code
if __name__ == '__main__':
k = 6
n = 4
m = 4
a=[[0, 5, 6, 0 ],
[3, -1, -1, 4],
[-1, 2, 1, -1],
[-1, -1,-1,-1]]
check(k, a, n, m)
# This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static void check(int k, int [,]a,
int n, int m)
{
int [,]cell = new int[k,2];
bool [,]visited = new bool[n,m];
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i, j] != 0
&& a[i, j] != -1) {
cell[count, 0] = i;
cell[count, 1] = j;
count++;
}
visited[i, j] = false;
}
}
// Arrays to make grid traversals easier
int []dx = { 0, 0, 1, -1 };
int []dy = { 1, -1, 0, 0 };
// Store number of components
int component = 0;
// Perform BFS and mark every cell
// by the component in which it belongs
for (int i = 0; i < k; i++) {
int x = cell[i, 0], y = cell[i, 1];
if (visited[x, y])
continue;
component++;
List<pair> cells = new List<pair>();
cells.Add(new pair(x, y));
visited[x, y] = true;
while (cells.Count != 0) {
pair z = cells[0];
cells.RemoveAt(0);
a[z.first,z.second] = component;
for (int j = 0; j < 4; j++) {
int new_x = z.first + dx[j];
int new_y = z.second + dy[j];
if (new_x < 0 || new_x >= n
|| new_y < 0 || new_y >= m)
continue;
if (visited[new_x,new_y]
|| a[new_x, new_y] == -1)
continue;
cells.Add(new pair(new_x, new_y));
visited[new_x, new_y] = true;
}
}
}
int maximum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i, j] == -1) {
HashSet<int> set = new HashSet<int>();
for (int kk = 0; kk < 4; kk++) {
int xx = i + dx[kk];
int yy = j + dy[kk];
if (xx < 0 || xx >= n
|| yy < 0 || yy >= m)
continue;
// if the cell doesn't
// belong to any component
if (a[xx, yy] <= 0)
continue;
set.Add(a[xx, yy]);
}
int s = set.Count;
maximum = Math.Max(s, maximum);
}
}
}
if (maximum == component) {
Console.Write("Yes\n");
}
else {
Console.Write("No\n");
}
}
public static void Main(String[] args)
{
int k = 6;
int n = 4, m = 4;
int [,]a
= { { 0, 5, 6, 0 },
{ 3, -1, -1, 4 },
{ -1, 2, 1, -1 },
{ -1, -1, -1, -1 } };
check(k, a, n, m);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the above approach
function check(k, a, n, m)
{
var cells = Array.from(
Array(k), () => Array(2).fill(0));
var visited = Array.from(
Array(n), () => Array(m).fill(0));
var count = 0;
for(var i = 0; i < n; i++)
{
for(var j = 0; j < m; j++)
{
if (a[i][j] != 0 && a[i][j] != -1)
{
cells[count][0] = i;
cells[count][1] = j;
count++;
}
visited[i][j] = false;
}
}
// Arrays to make grid traversals easier
var dx = [ 0, 0, 1, -1 ];
var dy = [ 1, -1, 0, 0 ];
// Store number of components
var component = 0;
// Perform BFS and mark every cell
// by the component in which it belongs
for(var i = 0; i < k; i++)
{
var x = cells[i][0], y = cells[i][1];
if (visited[x][y])
continue;
component++;
var cell = [];
cell.push([x, y]);
visited[x][y] = true;
while (cell.length != 0)
{
var z = cell[0];
cell.shift();
a[z[0]][z[1]] = component;
for(var j = 0; j < 4; j++)
{
var new_x = z[0] + dx[j];
var new_y = z[1] + dy[j];
if (new_x < 0 || new_x >= n ||
new_y < 0 || new_y >= m)
continue;
if (visited[new_x][new_y] ||
a[new_x][new_y] == -1)
continue;
cell.push([new_x, new_y]);
visited[new_x][new_y] = true;
}
}
}
var maximum = 0;
for(var i = 0; i < n; i++)
{
for(var j = 0; j < m; j++)
{
if (a[i][j] == -1)
{
var set = new Set();
for(var kk = 0; kk < 4; kk++)
{
var xx = i + dx[kk];
var yy = j + dy[kk];
if (xx < 0 || xx >= n ||
yy < 0 || yy >= m)
continue;
// If the cell doesn't
// belong to any component
if (a[xx][yy] <= 0)
continue;
set.add(a[xx][yy]);
}
var s = set.size;
maximum = Math.max(s, maximum);
}
}
}
if (maximum == component)
{
document.write("Yes");
}
else
{
document.write("No");
}
}
// Driver code
var k = 6;
var n = 4, m = 4;
var a = [ [ 0, 5, 6, 0 ],
[ 3, -1, -1, 4 ],
[ -1, 2, 1, -1 ],
[ -1, -1, -1, -1 ] ];
check(k, a, n, m);
// This code is contributed by itsok
</script>
Producción:
Yes
Análisis de rendimiento:
- Complejidad de tiempo: realizar BFS en la array requiere tiempo O (N * M) y tiempo O (N * M) para verificar cada celda bloqueada. Por lo tanto, la complejidad del tiempo total será O(N * M) .
- Complejidad del Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por jrishabh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA