Dada una array donde cada elemento es ‘O’ o ‘X’, reemplace ‘O’ con ‘X’ si está rodeado por ‘X’. Se considera que una ‘O’ (o un conjunto de ‘O’) está rodeada por una ‘X’ si hay ‘X’ en ubicaciones justo debajo, justo arriba, justo a la izquierda y justo a la derecha.
Ejemplos:
Input: mat[M][N] = {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'O', 'X'},
{'X', 'X', 'X', 'O', 'O', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
Output: mat[M][N] = {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X', 'X', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
Input: mat[M][N] = {{'X', 'X', 'X', 'X'}
{'X', 'O', 'X', 'X'}
{'X', 'O', 'O', 'X'}
{'X', 'O', 'X', 'X'}
{'X', 'X', 'O', 'O'}
};
Input: mat[M][N] = {{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'O', 'O'}
};
Esta es principalmente una aplicación del algoritmo Flood-Fill . La principal diferencia aquí es que una ‘O’ no se reemplaza por una ‘X’ si se encuentra en una región que termina en un límite. Los siguientes son pasos simples para hacer este relleno de inundación especial.
- Recorra la array dada y reemplace todas las ‘O’ con un carácter especial ‘-‘.
- Atraviese cuatro aristas de la array dada y llame a floodFill(‘-‘, ‘O’) para cada ‘-‘ en las aristas. Los ‘-‘ restantes son los caracteres que indican ‘O’s (en la array original) para ser reemplazados por ‘X’.
- Atraviese la array y reemplace todos los ‘-‘ con ‘X’.
Veamos los pasos del algoritmo anterior con un ejemplo. Sea lo siguiente la array de entrada.
mat[M][N] = {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'O', 'X'},
{'X', 'X', 'X', 'O', 'O', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
Paso 1: Reemplace todas las ‘O’ con ‘-‘.
mat[M][N] = {{'X', '-', 'X', 'X', 'X', 'X'},
{'X', '-', 'X', 'X', '-', 'X'},
{'X', 'X', 'X', '-', '-', 'X'},
{'-', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', '-', 'X', '-'},
{'-', '-', 'X', '-', '-', '-'},
};
Paso 2: Llame a floodFill(‘-‘, ‘O’) para todos los elementos de borde con valor igual a ‘-‘
mat[M][N] = {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', '-', 'X'},
{'X', 'X', 'X', '-', '-', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
Paso 3: Reemplace todos los ‘-‘ con ‘X’.
mat[M][N] = {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X', 'X', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
La siguiente es la implementación del algoritmo anterior.
C++
// A C++ program to replace all 'O's with 'X''s if surrounded by 'X'
#include<iostream>
using namespace std;
// Size of given matrix is M X N
#define M 6
#define N 6
// A recursive function to replace previous value 'prevV' at '(x, y)'
// and all surrounding values of (x, y) with new value 'newV'.
void floodFillUtil(char mat[][N], int x, int y, char prevV, char newV)
{
// Base cases
if (x < 0 || x >= M || y < 0 || y >= N)
return;
if (mat[x][y] != prevV)
return;
// Replace the color at (x, y)
mat[x][y] = newV;
// Recur for north, east, south and west
floodFillUtil(mat, x+1, y, prevV, newV);
floodFillUtil(mat, x-1, y, prevV, newV);
floodFillUtil(mat, x, y+1, prevV, newV);
floodFillUtil(mat, x, y-1, prevV, newV);
}
// Returns size of maximum size subsquare matrix
// surrounded by 'X'
int replaceSurrounded(char mat[][N])
{
// Step 1: Replace all 'O' with '-'
for (int i=0; i<M; i++)
for (int j=0; j<N; j++)
if (mat[i][j] == 'O')
mat[i][j] = '-';
// Call floodFill for all '-' lying on edges
for (int i=0; i<M; i++) // Left side
if (mat[i][0] == '-')
floodFillUtil(mat, i, 0, '-', 'O');
for (int i=0; i<M; i++) // Right side
if (mat[i][N-1] == '-')
floodFillUtil(mat, i, N-1, '-', 'O');
for (int i=0; i<N; i++) // Top side
if (mat[0][i] == '-')
floodFillUtil(mat, 0, i, '-', 'O');
for (int i=0; i<N; i++) // Bottom side
if (mat[M-1][i] == '-')
floodFillUtil(mat, M-1, i, '-', 'O');
// Step 3: Replace all '-' with 'X'
for (int i=0; i<M; i++)
for (int j=0; j<N; j++)
if (mat[i][j] == '-')
mat[i][j] = 'X';
}
// Driver program to test above function
int main()
{
char mat[][N] = {{'X', 'O', 'X', 'O', 'X', 'X'},
{'X', 'O', 'X', 'X', 'O', 'X'},
{'X', 'X', 'X', 'O', 'X', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
replaceSurrounded(mat);
for (int i=0; i<M; i++)
{
for (int j=0; j<N; j++)
cout << mat[i][j] << " ";
cout << endl;
}
return 0;
}
Java
// A Java program to replace
// all 'O's with 'X''s if
// surrounded by 'X'
import java.io.*;
class GFG
{
static int M = 6;
static int N = 6;
static void floodFillUtil(char mat[][], int x,
int y, char prevV,
char newV)
{
// Base cases
if (x < 0 || x >= M ||
y < 0 || y >= N)
return;
if (mat[x][y] != prevV)
return;
// Replace the color at (x, y)
mat[x][y] = newV;
// Recur for north,
// east, south and west
floodFillUtil(mat, x + 1, y,
prevV, newV);
floodFillUtil(mat, x - 1, y,
prevV, newV);
floodFillUtil(mat, x, y + 1,
prevV, newV);
floodFillUtil(mat, x, y - 1,
prevV, newV);
}
// Returns size of maximum
// size subsquare matrix
// surrounded by 'X'
static void replaceSurrounded(char mat[][])
{
// Step 1: Replace
// all 'O' with '-'
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
if (mat[i][j] == 'O')
mat[i][j] = '-';
// Call floodFill for
// all '-' lying on edges
for (int i = 0; i < M; i++) // Left side
if (mat[i][0] == '-')
floodFillUtil(mat, i, 0,
'-', 'O');
for (int i = 0; i < M; i++) // Right side
if (mat[i][N - 1] == '-')
floodFillUtil(mat, i, N - 1,
'-', 'O');
for (int i = 0; i < N; i++) // Top side
if (mat[0][i] == '-')
floodFillUtil(mat, 0, i,
'-', 'O');
for (int i = 0; i < N; i++) // Bottom side
if (mat[M - 1][i] == '-')
floodFillUtil(mat, M - 1,
i, '-', 'O');
// Step 3: Replace
// all '-' with 'X'
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
if (mat[i][j] == '-')
mat[i][j] = 'X';
}
// Driver Code
public static void main (String[] args)
{
char[][] mat = {{'X', 'O', 'X',
'O', 'X', 'X'},
{'X', 'O', 'X',
'X', 'O', 'X'},
{'X', 'X', 'X',
'O', 'X', 'X'},
{'O', 'X', 'X',
'X', 'X', 'X'},
{'X', 'X', 'X',
'O', 'X', 'O'},
{'O', 'O', 'X',
'O', 'O', 'O'}};
replaceSurrounded(mat);
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
System.out.print(mat[i][j] + " ");
System.out.println("");
}
}
}
// This code is contributed
// by shiv_bhakt
Python3
# Python3 program to replace all 'O's with # 'X's if surrounded by 'X' # Size of given matrix is M x N M = 6 N = 6 # A recursive function to replace previous # value 'prevV' at '(x, y)' and all surrounding # values of (x, y) with new value 'newV'. def floodFillUtil(mat, x, y, prevV, newV): # Base Cases if (x < 0 or x >= M or y < 0 or y >= N): return if (mat[x][y] != prevV): return # Replace the color at (x, y) mat[x][y] = newV # Recur for north, east, south and west floodFillUtil(mat, x + 1, y, prevV, newV) floodFillUtil(mat, x - 1, y, prevV, newV) floodFillUtil(mat, x, y + 1, prevV, newV) floodFillUtil(mat, x, y - 1, prevV, newV) # Returns size of maximum size subsquare # matrix surrounded by 'X' def replaceSurrounded(mat): # Step 1: Replace all 'O's with '-' for i in range(M): for j in range(N): if (mat[i][j] == 'O'): mat[i][j] = '-' # Call floodFill for all '-' # lying on edges # Left Side for i in range(M): if (mat[i][0] == '-'): floodFillUtil(mat, i, 0, '-', 'O') # Right side for i in range(M): if (mat[i][N - 1] == '-'): floodFillUtil(mat, i, N - 1, '-', 'O') # Top side for i in range(N): if (mat[0][i] == '-'): floodFillUtil(mat, 0, i, '-', 'O') # Bottom side for i in range(N): if (mat[M - 1][i] == '-'): floodFillUtil(mat, M - 1, i, '-', 'O') # Step 3: Replace all '-' with 'X' for i in range(M): for j in range(N): if (mat[i][j] == '-'): mat[i][j] = 'X' # Driver code if __name__ == '__main__': mat = [ [ 'X', 'O', 'X', 'O', 'X', 'X' ], [ 'X', 'O', 'X', 'X', 'O', 'X' ], [ 'X', 'X', 'X', 'O', 'X', 'X' ], [ 'O', 'X', 'X', 'X', 'X', 'X' ], [ 'X', 'X', 'X', 'O', 'X', 'O' ], [ 'O', 'O', 'X', 'O', 'O', 'O' ] ]; replaceSurrounded(mat) for i in range(M): print(*mat[i]) # This code is contributed by himanshu77
C#
// A C# program to replace
// all 'O's with 'X''s if
// surrounded by 'X'
using System;
class GFG
{
static int M = 6;
static int N = 6;
static void floodFillUtil(char [,]mat, int x,
int y, char prevV,
char newV)
{
// Base cases
if (x < 0 || x >= M ||
y < 0 || y >= N)
return;
if (mat[x, y] != prevV)
return;
// Replace the color at (x, y)
mat[x, y] = newV;
// Recur for north,
// east, south and west
floodFillUtil(mat, x + 1, y,
prevV, newV);
floodFillUtil(mat, x - 1, y,
prevV, newV);
floodFillUtil(mat, x, y + 1,
prevV, newV);
floodFillUtil(mat, x, y - 1,
prevV, newV);
}
// Returns size of maximum
// size subsquare matrix
// surrounded by 'X'
static void replaceSurrounded(char [,]mat)
{
// Step 1: Replace
// all 'O' with '-'
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
if (mat[i, j] == 'O')
mat[i, j] = '-';
// Call floodFill for
// all '-' lying on edges
for (int i = 0; i < M; i++) // Left side
if (mat[i, 0] == '-')
floodFillUtil(mat, i, 0,
'-', 'O');
for (int i = 0; i < M; i++) // Right side
if (mat[i, N - 1] == '-')
floodFillUtil(mat, i, N - 1,
'-', 'O');
for (int i = 0; i < N; i++) // Top side
if (mat[0, i] == '-')
floodFillUtil(mat, 0, i,
'-', 'O');
for (int i = 0; i < N; i++) // Bottom side
if (mat[M - 1, i] == '-')
floodFillUtil(mat, M - 1,
i, '-', 'O');
// Step 3: Replace
// all '-' with 'X'
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
if (mat[i, j] == '-')
mat[i, j] = 'X';
}
// Driver Code
public static void Main ()
{
char [,]mat = new char[,]
{{'X', 'O', 'X',
'O', 'X', 'X'},
{'X', 'O', 'X',
'X', 'O', 'X'},
{'X', 'X', 'X',
'O', 'X', 'X'},
{'O', 'X', 'X',
'X', 'X', 'X'},
{'X', 'X', 'X',
'O', 'X', 'O'},
{'O', 'O', 'X',
'O', 'O', 'O'}};
replaceSurrounded(mat);
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
Console.Write(mat[i, j] + " ");
Console.WriteLine("");
}
}
}
// This code is contributed
// by shiv_bhakt
PHP
<?php
// A PHP program to replace all
// 'O's with 'X''s if surrounded by 'X'
// Size of given
// matrix is M X N
$M = 6;
$N = 6;
// A recursive function to replace
// previous value 'prevV' at '(x, y)'
// and all surrounding values of
// (x, y) with new value 'newV'.
function floodFillUtil(&$mat, $x, $y,
$prevV, $newV)
{
// Base cases
if ($x < 0 || $x >= $GLOBALS['M'] ||
$y < 0 || $y >= $GLOBALS['N'])
return;
if ($mat[$x][$y] != $prevV)
return;
// Replace the color at (x, y)
$mat[$x][$y] = $newV;
// Recur for north,
// east, south and west
floodFillUtil($mat, $x + 1, $y, $prevV, $newV);
floodFillUtil($mat, $x - 1, $y, $prevV, $newV);
floodFillUtil($mat, $x, $y + 1, $prevV, $newV);
floodFillUtil($mat, $x, $y - 1, $prevV, $newV);
}
// Returns size of maximum
// size subsquare matrix
// surrounded by 'X'
function replaceSurrounded(&$mat)
{
// Step 1: Replace all 'O' with '-'
for ($i = 0; $i < $GLOBALS['M']; $i++)
for ($j = 0; $j < $GLOBALS['N']; $j++)
if ($mat[$i][$j] == 'O')
$mat[$i][$j] = '-';
// Call floodFill for all
// '-' lying on edges
for ($i = 0;
$i < $GLOBALS['M']; $i++) // Left side
if ($mat[$i][0] == '-')
floodFillUtil($mat, $i, 0, '-', 'O');
for ($i = 0; $i < $GLOBALS['M']; $i++) // Right side
if ($mat[$i][$GLOBALS['N'] - 1] == '-')
floodFillUtil($mat, $i,
$GLOBALS['N'] - 1, '-', 'O');
for ($i = 0; $i < $GLOBALS['N']; $i++) // Top side
if ($mat[0][$i] == '-')
floodFillUtil($mat, 0, $i, '-', 'O');
for ($i = 0; $i < $GLOBALS['N']; $i++) // Bottom side
if ($mat[$GLOBALS['M'] - 1][$i] == '-')
floodFillUtil($mat, $GLOBALS['M'] - 1,
$i, '-', 'O');
// Step 3: Replace all '-' with 'X'
for ($i = 0; $i < $GLOBALS['M']; $i++)
for ($j = 0; $j < $GLOBALS['N']; $j++)
if ($mat[$i][$j] == '-')
$mat[$i][$j] = 'X';
}
// Driver Code
$mat = array(array('X', 'O', 'X', 'O', 'X', 'X'),
array('X', 'O', 'X', 'X', 'O', 'X'),
array('X', 'X', 'X', 'O', 'X', 'X'),
array('O', 'X', 'X', 'X', 'X', 'X'),
array('X', 'X', 'X', 'O', 'X', 'O'),
array('O', 'O', 'X', 'O', 'O', 'O'));
replaceSurrounded($mat);
for ($i = 0; $i < $GLOBALS['M']; $i++)
{
for ($j = 0; $j < $GLOBALS['N']; $j++)
echo $mat[$i][$j]." ";
echo "\n";
}
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// A Javascript program to replace
// all 'O's with 'X''s if
// surrounded by 'X'
let M = 6;
let N = 6;
function floodFillUtil(mat,x,y,prevV,newV)
{
// Base cases
if (x < 0 || x >= M ||
y < 0 || y >= N)
return;
if (mat[x][y] != prevV)
return;
// Replace the color at (x, y)
mat[x][y] = newV;
// Recur for north,
// east, south and west
floodFillUtil(mat, x + 1, y,
prevV, newV);
floodFillUtil(mat, x - 1, y,
prevV, newV);
floodFillUtil(mat, x, y + 1,
prevV, newV);
floodFillUtil(mat, x, y - 1,
prevV, newV);
}
// Returns size of maximum
// size subsquare matrix
// surrounded by 'X'
function replaceSurrounded(mat)
{
// Step 1: Replace
// all 'O' with '-'
for (let i = 0; i < M; i++)
for (let j = 0; j < N; j++)
if (mat[i][j] == 'O')
mat[i][j] = '-';
// Call floodFill for
// all '-' lying on edges
for (let i = 0; i < M; i++) // Left side
if (mat[i][0] == '-')
floodFillUtil(mat, i, 0,
'-', 'O');
for (let i = 0; i < M; i++) // Right side
if (mat[i][N - 1] == '-')
floodFillUtil(mat, i, N - 1,
'-', 'O');
for (let i = 0; i < N; i++) // Top side
if (mat[0][i] == '-')
floodFillUtil(mat, 0, i,
'-', 'O');
for (let i = 0; i < N; i++) // Bottom side
if (mat[M - 1][i] == '-')
floodFillUtil(mat, M - 1,
i, '-', 'O');
// Step 3: Replace
// all '-' with 'X'
for (let i = 0; i < M; i++)
for (let j = 0; j < N; j++)
if (mat[i][j] == '-')
mat[i][j] = 'X';
}
// Driver Code
let mat = [ [ 'X', 'O', 'X', 'O', 'X', 'X' ],
[ 'X', 'O', 'X', 'X', 'O', 'X' ],
[ 'X', 'X', 'X', 'O', 'X', 'X' ],
[ 'O', 'X', 'X', 'X', 'X', 'X' ],
[ 'X', 'X', 'X', 'O', 'X', 'O' ],
[ 'O', 'O', 'X', 'O', 'O', 'O' ] ];
replaceSurrounded(mat);
for (let i = 0; i < M; i++)
{
for (let j = 0; j < N; j++)
document.write(mat[i][j] + " ");
document.write("<br>");
}
// This code is contributed by rag2127
</script>
Producción
X O X O X X X O X X X X X X X X X X O X X X X X X X X O X O O O X O O O
La complejidad temporal de la solución anterior es O(MN). Tenga en cuenta que cada elemento de la array se procesa como máximo tres veces.
Espacio auxiliar: O (M x N), ya que se usa la pila implícita debido a la llamada recursiva
Este artículo es una contribución de Aarti_Rathi y Anmol . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA