Dada una cuadrícula de tamaño (NxM) se debe llenar con números enteros.
El llenado de celdas en la grilla debe hacerse de la siguiente manera:
- sean A, B y C tres celdas y B y C compartan un lado con A.
- El valor de las celdas B y C debe ser distinto.
- Sea L el número de enteros distintos en una cuadrícula.
- Cada celda debe contener un valor de 1 a L.
La tarea es encontrar el valor mínimo de L y cualquier cuadrícula resultante.
Ejemplos:
Input: N = 1, M = 2
Output:
L = 2
grid = {1, 2}
Input: 2 3
Output:
L = 3
grid = {{1, 2, 3},
{1, 2, 3}}
Explanation: Integers in the neighbors
of cell (2, 2) are 1, 2 and 3.
All numbers are pairwise distinct.
Planteamiento:
Se da que dos celdas que comparten un lado con otra celda deben ser distintas. Para cada celda de este tipo, habrá un máximo posible de 8 celdas en una cuadrícula de las cuales su valor debe ser diferente.
Seguirá el problema de los 4 colores: el color máximo requerido para llenar las regiones será 4.
- Para N<4 o M<4
El número de números enteros requeridos puede variar de 1 a 4.
Marque 8 celdas y luego llene la celda actual.
Si el número de enteros distintos en 8 celdas es menor que L, llene la celda actual con cualquier número entero restante; de lo contrario, llene las celdas actuales con el número entero L+1. - Para N>=4 y M>=4
, el número de enteros requeridos debe ser 4 según el problema de 4 colores.
Use la array 4×4 para llenar la array NxM.1 2 3 4 1 2 3 4 3 4 1 2 3 4 1 2
A continuación se muestra la implementación del enfoque anterior:
Implementación:
# Python 3 implementation of
# above approach
# Function to display the matrix
def display_matrix(A):
for i in A:
print(*i)
# Function for calculation
def cal_main(A, L, x, i, j):
s = set()
# Checking 8 cells and
# then fill the current cell.
if (i - 2) >= 0:
s.add(A[i - 2][j])
if (i + 2) < N:
s.add(A[i + 2][j])
if (j - 2) >= 0:
s.add(A[i][j - 2])
if (j + 2) < M:
s.add(A[i][j + 2])
if (i - 1) >= 0 and (j - 1) >= 0:
s.add(A[i - 1][j - 1])
if (i - 1) >= 0 and (j + 1) < M:
s.add(A[i - 1][j + 1])
if (i + 1) < N and (j - 1) >= 0:
s.add(A[i + 1][j - 1])
if (i + 1) < N and (j + 1) < M:
s.add(A[i + 1][j + 1])
# Set to contain distinct value
# of integers in 8 cells.
s = s.difference({0})
if len(s) < L:
# Set contain remaining integers
w = x.difference(s)
# fill the current cell
# with maximum remaining integer
A[i][j] = max(w)
else:
# fill the current cells with L + 1 integer.
A[i][j] = L + 1
L += 1
# Increase the value of L
x.add(L)
return A, L, x
# Function to find the number
# of distinct integers
def solve(N, M):
# initialise the list (NxM) with 0.
A = []
for i in range(N):
K = []
for j in range(M):
K.append(0)
A.append(K)
# Set to contain distinct
# value of integers from 1-L
x = set()
L = 0
# Number of integer required
# may vary from 1 to 4.
if N < 4 or M < 4:
if N > M: # if N is greater
for i in range(N):
for j in range(M):
cal_main(A, L, x, i, j)
else:
# if M is greater
for j in range(M):
for i in range(N):
cal_main(A, L, x, i, j)
else:
# Number of integer required
# must be 4
L = 4
# 4×4 matrix to fill the NxM matrix.
m4 = [[1, 2, 3, 4],
[1, 2, 3, 4],
[3, 4, 1, 2],
[3, 4, 1, 2]]
for i in range(4):
for j in range(4):
A[i][j] = m4[i][j]
for i in range(4, N):
for j in range(4):
A[i][j] = m4[i % 4][j]
for j in range(4, M):
for i in range(N):
A[i][j] = A[i][j % 4]
print(L)
display_matrix(A)
# Driver Code
if __name__ == "__main__":
# sample input
# Number of rows and columns
N, M = 10, 5
solve(N, M)
4 1 2 3 4 1 2 3 4 1 2 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 1 2 3 4 1 2 3 4 1 2
Publicación traducida automáticamente
Artículo escrito por SHUBHAMSINGH10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA