Dada una array arr[][] de dimensiones N * M , que consta de ‘O’ o ‘F’ , donde ‘O’ denota obstáculos y ‘F’ denota espacios libres, la tarea es reemplazar todas las ‘F’ en el array dada por ‘1’ o ‘2’ , de modo que no haya dos celdas adyacentes que tengan el mismo valor.
Ejemplos:
Entrada: N = 4, M = 4, array[][] = {{‘F’, ‘F’, ‘F’, ‘F’}, {‘F’, ‘O’, ‘F’, ‘F ‘}, {‘F’, ‘F’, ‘O’, ‘F’}, {‘F’, ‘F’, ‘F’, ‘F’}}
Salida:
1 2 1 2
2 O 2 1
1 2 O 2
2 1 2 1Entrada: N = 1, M = 1, arr[][] = {{‘O’}}
Salida:
Enfoque ingenuo: el enfoque más simple para resolver el problema es usar Backtracking , similar al problema de Sudoku . Pero, en lugar de colocar N valores diferentes en una posición determinada, se requiere que se coloquen 1 o 2 en las celdas que contienen ‘F’ de modo que no haya dos elementos adyacentes iguales entre sí. Siga los pasos a continuación para resolver el problema:
- Cree una función para verificar si la posición dada en la array es válida o no.
- Si se ha alcanzado el final de la array, es decir, i = N y j = M , devuelva True .
- De lo contrario, si el índice actual es un espacio libre, es decir, arr[i][j]==’F’ , complete el índice con ‘1’ o ‘2’ . Si se determina que alguna celda no es válida, es decir, cualquiera de sus celdas adyacentes tiene el mismo valor, imprima “No” .
- Después de completar el recorrido de la array, si todas las ‘F’ se reemplazaron de manera que ningún elemento adyacente de la array sea el mismo, imprima «Sí» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if current
// position is safe or not
bool issafe(vector<vector<char> >& v, int i,
int j, int n, int m, char ch)
{
// Directions for adjacent cells
int rowN[] = { 1, -1, 0, 0 };
int colN[] = { 0, 0, 1, -1 };
for (int k = 0; k < 4; k++) {
// Check if any adjacent cell is same
if (i + rowN[k] >= 0 && i + rowN[k] < n
&& j + colN[k] >= 0 && j + colN[k] < m
&& v[i + rowN[k]][j + colN[k]] == ch) {
return false;
}
}
// Current index is valid
return true;
}
// Recursive function for backtracking
bool place(vector<vector<char> >& v,
int n, int m)
{
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
// Free cell
if (v[i][j] == 'F') {
break;
}
}
if (j != m) {
break;
}
}
// All positions covered
if (i == n && j == m) {
return true;
}
// If position is valid for 1
if (issafe(v, i, j, n, m, '1')) {
v[i][j] = '1';
if (place(v, n, m)) {
return true;
}
v[i][j] = 'F';
}
// If position is valid for 2
if (issafe(v, i, j, n, m, '2')) {
v[i][j] = '2';
// Recursive call for next
// unoccupied position
if (place(v, n, m)) {
return true;
}
// If above conditions fails
v[i][j] = 'F';
}
return false;
}
// Function to print valid matrix
void printMatrix(vector<vector<char> > arr,
int n, int m)
{
place(arr, n, m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << arr[i][j];
}
cout << endl;
}
}
// Driver Code
int main()
{
// Given matrix
vector<vector<char> > arr = {
{ 'F', 'F', 'F', 'F' },
{ 'F', 'O', 'F', 'F' },
{ 'F', 'F', 'O', 'F' },
{ 'F', 'F', 'F', 'F' },
};
// Give dimensions
int n = 4, m = 4;
// Function call
printMatrix(arr, n, m);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
public static boolean issafe(char v[][], int i,
int j, int n, int m, char ch)
{
// Directions for adjacent cells
int rowN[] = { 1, -1, 0, 0 };
int colN[] = { 0, 0, 1, -1 };
for (int k = 0; k < 4; k++) {
// Check if any adjacent cell is same
if (i + rowN[k] >= 0 && i + rowN[k] < n
&& j + colN[k] >= 0 && j + colN[k] < m
&& v[i + rowN[k]][j + colN[k]] == ch) {
return false;
}
}
// Current index is valid
return true;
}
// Recursive function for backtracking
public static boolean place(char v[][],
int n, int m)
{
int i=0, j=0;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
// Free cell
if (v[i][j] == 'F') {
break;
}
}
if (j != m) {
break;
}
}
// All positions covered
if (i == n && j == m) {
return true;
}
// If position is valid for 1
if (issafe(v, i, j, n, m, '1')) {
v[i][j] = '1';
if (place(v, n, m)) {
return true;
}
v[i][j] = 'F';
}
// If position is valid for 2
if (issafe(v, i, j, n, m, '2')) {
v[i][j] = '2';
// Recursive call for next
// unoccupied position
if (place(v, n, m)) {
return true;
}
// If above conditions fails
v[i][j] = 'F';
}
return false;
}
// Function to print valid matrix
public static void printMatrix(char arr[][],
int n, int m)
{
place(arr, n, m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
}
// Driver Code
public static void main (String[] args) {
char arr[][] = {
{ 'F', 'F', 'F', 'F' },
{ 'F', 'O', 'F', 'F' },
{ 'F', 'F', 'O', 'F' },
{ 'F', 'F', 'F', 'F' },
};
// Give dimensions
int n = 4, m = 4;
// Function call
printMatrix(arr, n, m);
}
}
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if current
// position is safe or not
public static bool issafe(char[,] v, int i,
int j, int n,
int m, char ch)
{
// Directions for adjacent cells
int[] rowN = { 1, -1, 0, 0 };
int[] colN = { 0, 0, 1, -1 };
for(int k = 0; k < 4; k++)
{
// Check if any adjacent cell is same
if (i + rowN[k] >= 0 && i + rowN[k] < n &&
j + colN[k] >= 0 && j + colN[k] < m &&
v[(i + rowN[k]), (j + colN[k])] == ch)
{
return false;
}
}
// Current index is valid
return true;
}
// Recursive function for backtracking
public static bool place(char[,] v,
int n, int m)
{
int i = 0, j = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
// Free cell
if (v[i, j] == 'F')
{
break;
}
}
if (j != m)
{
break;
}
}
// All positions covered
if (i == n && j == m)
{
return true;
}
// If position is valid for 1
if (issafe(v, i, j, n, m, '1'))
{
v[i, j] = '1';
if (place(v, n, m))
{
return true;
}
v[i, j] = 'F';
}
// If position is valid for 2
if (issafe(v, i, j, n, m, '2'))
{
v[i, j] = '2';
// Recursive call for next
// unoccupied position
if (place(v, n, m))
{
return true;
}
// If above conditions fails
v[i, j] = 'F';
}
return false;
}
// Function to print valid matrix
public static void printMatrix(char[,] arr,
int n, int m)
{
place(arr, n, m);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
Console.Write(arr[i, j]);
}
Console.WriteLine();
}
}
// Driver Code
public static void Main()
{
char[,] arr = { { 'F', 'F', 'F', 'F' },
{ 'F', 'O', 'F', 'F' },
{ 'F', 'F', 'O', 'F' },
{ 'F', 'F', 'F', 'F' },};
// Give dimensions
int n = 4, m = 4;
// Function call
printMatrix(arr, n, m);
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program to implement
// the above approach
function issafe(v, i,
j, n, m, ch)
{
// Directions for adjacent cells
let rowN = [ 1, -1, 0, 0 ];
let colN = [ 0, 0, 1, -1 ];
for (let k = 0; k < 4; k++) {
// Check if any adjacent cell is same
if (i + rowN[k] >= 0 && i + rowN[k] < n
&& j + colN[k] >= 0 && j + colN[k] < m
&& v[i + rowN[k]][j + colN[k]] == ch) {
return false;
}
}
// Current index is valid
return true;
}
// Recursive function for backtracking
function place(v, n, m)
{
let i=0, j=0;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
// Free cell
if (v[i][j] == 'F') {
break;
}
}
if (j != m) {
break;
}
}
// All positions covered
if (i == n && j == m) {
return true;
}
// If position is valid for 1
if (issafe(v, i, j, n, m, '1')) {
v[i][j] = '1';
if (place(v, n, m)) {
return true;
}
v[i][j] = 'F';
}
// If position is valid for 2
if (issafe(v, i, j, n, m, '2')) {
v[i][j] = '2';
// Recursive call for next
// unoccupied position
if (place(v, n, m)) {
return true;
}
// If above conditions fails
v[i][j] = 'F';
}
return false;
}
// Function to print valid matrix
function printMatrix(arr,
n, m)
{
place(arr, n, m);
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
document.write(arr[i][j]);
}
document.write("<br/>");
}
}
// Driver code
let arr = [
[ 'F', 'F', 'F', 'F' ],
[ 'F', 'O', 'F', 'F' ],
[ 'F', 'F', 'O', 'F' ],
[ 'F', 'F', 'F', 'F' ],
];
// Give dimensions
let n = 4, m = 4;
// Function call
printMatrix(arr, n, m);
</script>
Producción
1212 2O21 12O2 2121
Complejidad de Tiempo: O(2 N*M )
Espacio Auxiliar: O(N*M)
Enfoque eficiente: la idea es simplemente reemplazar cualquier ‘F’ por 1 si la paridad de la celda (i, j) es 1 , es decir, (i + j) % 2 es 1 . De lo contrario, reemplace esa ‘F’ por 2 . Siga los pasos a continuación para resolver el problema:
- Recorrer la array dada .
- Para cada celda (i, j) recorrida, si la celda arr[i][j] es igual a ‘F’ y (i + j) % 2 es igual a 1 , asigne arr[i][j] = 1 . De lo contrario, asigne arr[i][j] = 2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to display the valid matrix
void print(vector<vector<char> > arr, int n, int m)
{
// Traverse the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char a = arr[i][j];
// If the current cell is a free
// space and is even-indexed
if ((i + j) % 2 == 0 && a == 'F') {
arr[i][j] = '1';
}
// If the current cell is a free
// space and is odd-indexed
else if (a == 'F') {
arr[i][j] = '2';
}
}
}
// Print the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << arr[i][j];
}
cout << endl;
}
}
// Driver Code
int main()
{
// Given N and M
int n = 4, m = 4;
// Given matrix
vector<vector<char> > arr = {
{ 'F', 'F', 'F', 'F' },
{ 'F', 'O', 'F', 'F' },
{ 'F', 'F', 'O', 'F' },
{ 'F', 'F', 'F', 'F' },
};
// Function call
print(arr, n, m);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to display the valid matrix
public static void print(char arr[][], int n, int m)
{
// Traverse the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char a = arr[i][j];
// If the current cell is a free
// space and is even-indexed
if ((i + j) % 2 == 0 && a == 'F') {
arr[i][j] = '1';
}
// If the current cell is a free
// space and is odd-indexed
else if (a == 'F') {
arr[i][j] = '2';
}
}
}
// Print the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
}
// Driver Code
public static void main (String[] args) {
// Given N and M
int n = 4, m = 4;
// Given matrix
char arr[][] = {
{ 'F', 'F', 'F', 'F' },
{ 'F', 'O', 'F', 'F' },
{ 'F', 'F', 'O', 'F' },
{ 'F', 'F', 'F', 'F' }};
// Function call
print(arr, n, m);
}
}
Python3
# Python3 program for the above approach # Function to display the valid matrix def Print(arr, n, m): # Traverse the matrix for i in range(n): for j in range(m): a = arr[i][j] # If the current cell is a free # space and is even-indexed if ((i + j) % 2 == 0 and a == 'F') : arr[i][j] = '1' # If the current cell is a free # space and is odd-indexed elif (a == 'F') : arr[i][j] = '2' # Print the matrix for i in range(n) : for j in range(m) : print(arr[i][j], end = "") print() # Given N and M n, m = 4, 4 # Given matrix arr = [ [ 'F', 'F', 'F', 'F' ], [ 'F', 'O', 'F', 'F' ], [ 'F', 'F', 'O', 'F' ], [ 'F', 'F', 'F', 'F' ]] # Function call Print(arr, n, m) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
class GFG{
// Function to display the valid matrix
public static void print(char[,] arr, int n,
int m)
{
// Traverse the matrix
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
char a = arr[i, j];
// If the current cell is a free
// space and is even-indexed
if ((i + j) % 2 == 0 && a == 'F')
{
arr[i, j] = '1';
}
// If the current cell is a free
// space and is odd-indexed
else if (a == 'F')
{
arr[i, j] = '2';
}
}
}
// Print the matrix
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
Console.Write(arr[i, j]);
}
Console.WriteLine();
}
}
// Driver Code
public static void Main()
{
// Given N and M
int n = 4, m = 4;
// Given matrix
char[,] arr = { { 'F', 'F', 'F', 'F' },
{ 'F', 'O', 'F', 'F' },
{ 'F', 'F', 'O', 'F' },
{ 'F', 'F', 'F', 'F' }};
// Function call
print(arr, n, m);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Java Script program for the above approach
// Function to display the valid matrix
function print(arr,n,m)
{
// Traverse the matrix
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
let a = arr[i][j];
// If the current cell is a free
// space and is even-indexed
if ((i + j) % 2 == 0 && a == 'F') {
arr[i][j] = '1';
}
// If the current cell is a free
// space and is odd-indexed
else if (a == 'F') {
arr[i][j] = '2';
}
}
}
// Print the matrix
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
document.write(arr[i][j]);
}
document.write("<br>");
}
}
// Driver Code
// Given N and M
let n = 4, m = 4;
// Given matrix
let arr = [
['F', 'F', 'F', 'F' ],
[ 'F', 'O', 'F', 'F' ],
[ 'F', 'F', 'O', 'F' ],
[ 'F', 'F', 'F', 'F' ]];
// Function call
print(arr, n, m);
// This code is contributed by sravan.
</script>
Producción
1212 2O21 12O2 2121
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA