Dada una array binaria V[][] de dimensiones N * M , en la que cada celda está vacía o bloqueada marcada con un 0 y un 1 respectivamente, la tarea es contar el número de formas de seleccionar K celdas vacías consecutivas de la misma fila o columna.
Ejemplos:
Entrada: V[][] = {{1, 1, 0}, {0, 0, 0}}, K = 2
Salida: 3
Explicación:
considerando la indexación basada en 1, se pueden seleccionar 2 celdas vacías consecutivas en lo siguiente formas:
[(1, 3), (2, 3)], [(2, 1), (2, 2)], [(2, 2), (2, 3)]
Entrada: V[][] = {{1, 1, 0}, {0, 0, 0}, {0, 0, 0}}, K = 1
Salida: 9
Explicación:
Es posible seleccionar todas las celdas ya que todas las celdas están vacías.
Enfoque:
la idea es recorrer la array en filas y, para cada fila, contar el número total de celdas consecutivas vacías.
Siga los pasos a continuación para resolver el problema:
- Recorra la array en filas y cuente el número de celdas consecutivas. Si el conteo llega a ser igual o superior a K, aumente el conteo en 1.
- Cada vez que se encuentra una celda bloqueada, restablece el recuento de celdas vacías consecutivas a 0.
- Repita los pasos anteriores mientras recorre la array en forma de columna también si K ? 1.
- Devolver el recuento final de células obtenidas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find no of ways
// to select K consecutive empty
// cells from a row or column
#include <bits/stdc++.h>
using namespace std;
// Function to Traverse
// the matrix row wise
int rowWise(char* v, int n,
int m, int k)
{
// Initialize ans
int ans = 0;
// Traverse row wise
for (int i = 0; i < n; i++) {
// Initialize no of
// consecutive empty
// cells
int countcons = 0;
for (int j = 0; j < m; j++) {
// Check if blocked cell is
// encountered then reset
// countcons to 0
if (*(v + i * m + j) == '1') {
countcons = 0;
}
// Check if empty cell is
// encountered, then
// increment countcons
else {
countcons++;
}
// Check if number of empty
// consecutive cells
// is greater or equal
// to K, increment the ans
if (countcons >= k) {
ans++;
}
}
}
// Return the count
return ans;
}
// Function to Traverse the
// matrix column wise
int colWise(char* v, int n,
int m, int k)
{
// Initialize ans
int ans = 0;
// Traverse column wise
for (int i = 0; i < m; i++) {
// Initialize no of
// consecutive empty cells
int countcons = 0;
for (int j = 0; j < n; j++) {
// Check if blocked cell is
// encountered then reset
// countcons to 0
if (*(v + j * n + i) == '1') {
countcons = 0;
}
// Check if empty cell is
// encountered, increment
// countcons
else {
countcons++;
}
// Check if number of empty
// consecutive cells
// is greater than or equal
// to K, increment the ans
if (countcons >= k) {
ans++;
}
}
}
// Return the count
return ans;
}
// Driver Code
int main()
{
int n = 3, m = 3, k = 1;
char v[n][m] = { '0', '0', '0',
'0', '0', '0',
'0', '0', '0' };
// If k = 1 only traverse row wise
if (k == 1) {
cout << rowWise(v[0], n, m, k);
}
// Traverse both row and column wise
else {
cout << colWise(v[0], n, m, k)
+ rowWise(v[0], n,
m, k);
}
return 0;
}
Java
// Java program to find no of ways
// to select K consecutive empty
// cells from a row or column
import java.util.*;
class GFG{
// Function to Traverse
// the matrix row wise
static int rowWise(char [][]v, int n,
int m, int k)
{
// Initialize ans
int ans = 0;
// Traverse row wise
for(int i = 0; i < n; i++)
{
// Initialize no of
// consecutive empty
// cells
int countcons = 0;
for(int j = 0; j < m; j++)
{
// Check if blocked cell is
// encountered then reset
// countcons to 0
if (v[i][j] == '1')
{
countcons = 0;
}
// Check if empty cell is
// encountered, then
// increment countcons
else
{
countcons++;
}
// Check if number of empty
// consecutive cells
// is greater or equal
// to K, increment the ans
if (countcons >= k)
{
ans++;
}
}
}
// Return the count
return ans;
}
// Function to Traverse the
// matrix column wise
static int colWise(char [][]v, int n,
int m, int k)
{
// Initialize ans
int ans = 0;
// Traverse column wise
for(int i = 0; i < m; i++)
{
// Initialize no of
// consecutive empty cells
int countcons = 0;
for(int j = 0; j < n; j++)
{
// Check if blocked cell is
// encountered then reset
// countcons to 0
if (v[j][i] == '1')
{
countcons = 0;
}
// Check if empty cell is
// encountered, increment
// countcons
else
{
countcons++;
}
// Check if number of empty
// consecutive cells
// is greater than or equal
// to K, increment the ans
if (countcons >= k)
{
ans++;
}
}
}
// Return the count
return ans;
}
// Driver Code
public static void main(String[] args)
{
int n = 3, m = 3, k = 1;
char v[][] = { { '0', '0', '0' },
{ '0', '0', '0' },
{ '0', '0', '0' } };
// If k = 1 only traverse row wise
if (k == 1)
{
System.out.print(rowWise(v, n, m, k));
}
// Traverse both row and column wise
else
{
System.out.print(colWise(v, n, m, k) +
rowWise(v, n, m, k));
}
}
}
// This code is contributed by amal kumar choubey
Python3
# Python 3 program to find no of ways # to select K consecutive empty # cells from a row or column # Function to Traverse # the matrix row wise def rowWise(v, n, m, k): # Initialize ans ans = 0 # Traverse row wise for i in range (n): # Initialize no of # consecutive empty # cells countcons = 0 for j in range (m): # Check if blocked cell is # encountered then reset # countcons to 0 if (v[i][j] == '1'): countcons = 0 # Check if empty cell is # encountered, then # increment countcons else: countcons += 1 # Check if number of empty # consecutive cells # is greater or equal # to K, increment the ans if (countcons >= k): ans += 1 # Return the count return ans # Function to Traverse the # matrix column wise def colWise(v, n, m, k): # Initialize ans ans = 0 # Traverse column wise for i in range (m): # Initialize no of # consecutive empty cells countcons = 0 for j in range (n): # Check if blocked cell is # encountered then reset # countcons to 0 if (v[j][i] == '1'): countcons = 0 # Check if empty cell is # encountered, increment # countcons else: countcons += 1 # Check if number of empty # consecutive cells # is greater than or equal # to K, increment the ans if (countcons >= k): ans += 1 # Return the count return ans # Driver Code if __name__ == "__main__": n = 3 m = 3 k = 1 v = [['0', '0', '0'], ['0', '0', '0'], ['0', '0', '0']] # If k = 1 only # traverse row wise if (k == 1): print (rowWise(v, n, m, k)) # Traverse both row # and column wise else: print (colWise(v, n, m, k) + rowWise(v, n, m, k)) # This code is contributed by Chitranayal
C#
// C# program to find no of ways
// to select K consecutive empty
// cells from a row or column
using System;
class GFG{
// Function to Traverse
// the matrix row wise
static int rowWise(char [,]v, int n,
int m, int k)
{
// Initialize ans
int ans = 0;
// Traverse row wise
for(int i = 0; i < n; i++)
{
// Initialize no of
// consecutive empty
// cells
int countcons = 0;
for(int j = 0; j < m; j++)
{
// Check if blocked cell is
// encountered then reset
// countcons to 0
if (v[i, j] == '1')
{
countcons = 0;
}
// Check if empty cell is
// encountered, then
// increment countcons
else
{
countcons++;
}
// Check if number of empty
// consecutive cells
// is greater or equal
// to K, increment the ans
if (countcons >= k)
{
ans++;
}
}
}
// Return the count
return ans;
}
// Function to Traverse the
// matrix column wise
static int colWise(char [,]v, int n,
int m, int k)
{
// Initialize ans
int ans = 0;
// Traverse column wise
for(int i = 0; i < m; i++)
{
// Initialize no of
// consecutive empty cells
int countcons = 0;
for(int j = 0; j < n; j++)
{
// Check if blocked cell is
// encountered then reset
// countcons to 0
if (v[j, i] == '1')
{
countcons = 0;
}
// Check if empty cell is
// encountered, increment
// countcons
else
{
countcons++;
}
// Check if number of empty
// consecutive cells
// is greater than or equal
// to K, increment the ans
if (countcons >= k)
{
ans++;
}
}
}
// Return the count
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int n = 3, m = 3, k = 1;
char [,]v = { { '0', '0', '0' },
{ '0', '0', '0' },
{ '0', '0', '0' } };
// If k = 1 only traverse row wise
if (k == 1)
{
Console.Write(rowWise(v, n, m, k));
}
// Traverse both row and column wise
else
{
Console.Write(colWise(v, n, m, k) +
rowWise(v, n, m, k));
}
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript program to find no of ways
// to select K consecutive empty
// cells from a row or column
// Function to Traverse
// the matrix row wise
function rowWise(v, n, m, k)
{
// Initialize ans
var ans = 0;
// Traverse row wise
for (var i = 0; i < n; i++) {
// Initialize no of
// consecutive empty
// cells
var countcons = 0;
for (var j = 0; j < m; j++) {
// Check if blocked cell is
// encountered then reset
// countcons to 0
if ((v + i * m + j) == '1') {
countcons = 0;
}
// Check if empty cell is
// encountered, then
// increment countcons
else {
countcons++;
}
// Check if number of empty
// consecutive cells
// is greater or equal
// to K, increment the ans
if (countcons >= k) {
ans++;
}
}
}
// Return the count
return ans;
}
// Function to Traverse the
// matrix column wise
function colWise(v, n, m, k)
{
// Initialize ans
var ans = 0;
// Traverse column wise
for (var i = 0; i < m; i++) {
// Initialize no of
// consecutive empty cells
var countcons = 0;
for (var j = 0; j < n; j++) {
// Check if blocked cell is
// encountered then reset
// countcons to 0
if ((v + j * n + i) == '1') {
countcons = 0;
}
// Check if empty cell is
// encountered, increment
// countcons
else {
countcons++;
}
// Check if number of empty
// consecutive cells
// is greater than or equal
// to K, increment the ans
if (countcons >= k) {
ans++;
}
}
}
// Return the count
return ans;
}
// Driver Code
var n = 3, m = 3, k = 1;
var v = ['0', '0', '0',
'0', '0', '0',
'0', '0', '0'];
// If k = 1 only traverse row wise
if (k == 1) {
document.write( rowWise(v[0], n, m, k));
}
// Traverse both row and column wise
else {
document.write( colWise(v[0], n, m, k)
+ rowWise(v[0], n,
m, k));
}
// This code is contributed by itsok.
</script>
Producción:
9
Complejidad de tiempo: O(N * M)
Complejidad de espacio: O(N * M)
Publicación traducida automáticamente
Artículo escrito por nishitsharma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA