algorithm - pro - Maestro de buscaminas de Google Code Jam(2014) Ronda de clasificación
descargar buscaminas clasico (11)
Pre-cheques
M = (R * C) - 1
Rellena la cuadrícula con todas las minas y pon clic en cualquier lugar.
R == 1 || C == 1
Rellene izquierda / derecha (o arriba / abajo) en orden: haga clic en, no minas, minas (ej. c...**** ).
M == (R * C) - 2 || M == (R * C) - 3
Imposible
Algoritmo
Comencé con una cuadrícula "vacía" (todos . S) y coloqué el clic en una esquina (usaré la esquina superior izquierda para el clic y comenzaré a llenar las minas de la parte inferior derecha).
Usaremos R1 y C1 como nuestras filas y columnas "actuales".
Si bien tenemos suficientes minas para llenar una fila o columna que, cuando se elimina, no deja una sola fila o columna a la izquierda ( while((M >= R1 && C1 > 2) || (M >= C1 && R1 > 2)) ), "recortamos" la cuadrícula (rellenamos con minas y reducimos R1 o C1 ) utilizando el lado más corto y eliminamos esa cantidad de minas. Por lo tanto, un 4x5 con 6 minas restantes se convertiría en un 4x4 con 2 minas restantes.
- Si terminamos con una cuadrícula de 2 xn, tendremos 0 minas (ya terminamos) o 1 mina (Imposible ganar).
- Si terminamos con una cuadrícula de 3 x 3 tendremos 0 minas (ya terminamos), 1 mina (continúe abajo) o 2 minas (Imposible ganar).
- Cualquier otra combinación es ganable. Verificamos si
M == min(R1,C1)-1, si es así, necesitaremos colocar una sola fila o columna de una mina desde el borde más corto, luego llenar el borde más corto con las minas restantes.
Ejemplo
Mostraré el orden en el que entro las minas en la cuadrícula con números, solo para ayudar con la visualización
R = 7, C = 6, M = 29
c...42
....42
...742
..6742
555542
333332
111111
Me tomó varios intentos diferentes para corregir mi algoritmo, pero escribí el mío en PHP y obtuve tanto el pequeño como el gran correcto.
Este es un problema de la ronda de calificación de Google Code Jam (que ya terminó). ¿Cómo resolver este problema?
Nota: Si tiene un método diferente de los que se analizan en las respuestas, compártalos para que podamos ampliar nuestro conocimiento de las diferentes maneras de resolver este problema.
Buscaminas es un juego de computadora que se hizo popular en la década de 1980 y aún se incluye en algunas versiones del sistema operativo Microsoft Windows. Este problema tiene una idea similar, pero no supone que hayas jugado al Buscaminas.
En este problema, estás jugando un juego en una cuadrícula de celdas idénticas. El contenido de cada celda está inicialmente oculto. Hay M minas ocultas en M celdas diferentes de la red. Ninguna otra celda contiene minas. Puedes hacer clic en cualquier celda para revelarlo. Si la celda revelada contiene una mina, entonces el juego termina y tú pierdes. De lo contrario, la celda revelada contendrá un dígito entre 0 y 8, inclusive, que corresponde al número de celdas vecinas que contienen minas. Dos celdas son vecinas si comparten una esquina o un borde. Además, si la celda revelada contiene un 0, entonces todos los vecinos de la celda revelada también se revelan automáticamente, recursivamente. Cuando todas las celdas que no contienen minas han sido reveladas, el juego termina y tú ganas.
Por ejemplo, una configuración inicial de la placa puede tener este aspecto (''*'' denota una mina, y ''c'' es la primera celda en la que se hizo clic):
*..*...**.
....*.....
..c..*....
........*.
..........
No hay minas adyacentes a la celda en la que se hizo clic, por lo que cuando se revela, se convierte en un 0, y sus 8 celdas adyacentes también se revelan. Este proceso continúa, resultando en la siguiente tabla:
*..*...**.
1112*.....
00012*....
00001111*.
00000001..
En este punto, todavía hay celdas no reveladas que no contienen minas (indicadas por los caracteres "."), Por lo que el jugador debe hacer clic nuevamente para continuar el juego.
Quieres ganar el juego lo más rápido posible. No hay nada más rápido que ganar en un clic. Dado el tamaño del tablero (R x C) y el número de minas ocultas M, ¿es posible (aunque sea poco probable) ganar con un solo clic? Puede elegir donde hace clic. Si es posible, imprima cualquier configuración de mina válida y las coordenadas de su clic, siguiendo las especificaciones en la sección Salida. De lo contrario, imprima "Imposible".
Mi solución probada:
Entonces, para la solución, debe asegurarse de que cada nodo no minado esté en una matriz de 3x3 con otros nodos no minados, o una matriz de 3x2 o 2x2 si el nodo está en un borde de la cuadrícula; Llamemos a esto un 0Matrix. Entonces, cualquier nodo en un 0Matrix tiene todos los vecinos que no son de la mina
En primer lugar, compruebe si se requieren menos minas o menos nodos vacíos
if(# mines required < 1/3 of total grid size)
// Initialize the grid to all clear nodes and populate the mines
foreach (Node A : the set of non-mine nodes)
foreach (Node AN : A.neighbors)
if AN forms a OMatrix with it''s neighbors, continue
else break;
// If we got here means we can make A a mine since all of it''s neighbors
// form 0Matricies with their other neighbors
// End this loop when we''ve added the number of mines required
else
// We initialize the grid to all mines and populate the clear nodes
// Here I handle grids > 3x3;
// For smaller grids, I hard coded the logic, eg: 1xn grids, you just populate in 1 dimension
// Now we know that the # clear nodes required will be 3n+2 or 3n+4
// eg: if a 4x4 grid need 8 clear nodes : 3(2) + 2
For (1 -> num 3''s needed)
Add 3 nodes going horizontally
When horizontal axis is filled, add 3 nodes going vertically
When vertical axis is filled, go back to horizontal then vertical and so on.
for(1 -> num 2''s needed)
Add 2 nodes going horizontally or continuing in the direction from above
When horizontal axis is filled, add 2 nodes going vertically
Por ejemplo, digamos que tenemos una cuadrícula 4x4 que necesita 8 nodos limpios, aquí están los pasos:
// Initial grid of all mines
* * * *
* * * *
* * * *
* * * *
// Populating 3''s horizontally
. * * *
. * * *
. * * *
* * * *
. . * *
. . * *
. . * *
* * * *
// Populating 2''s continuing in the same direction as 3''s
. . . *
. . . *
. . * *
* * * *
Otro ejemplo: cuadrícula 4x4 con 11 nodos claros necesarios; salida:
. . . .
. . . .
. . . *
* * * *
Otro ejemplo: cuadrícula 4x4 con 14 nodos claros necesarios; salida:
// Insert the 4 3''s horizontally, then switch to vertical to insert the 2''s
. . . .
. . . .
. . . .
. . * *
Ahora aquí tenemos una cuadrícula que está completamente poblada y se puede resolver con un clic si hacemos clic en (0, 0).
Mi solución funciona para la mayoría de los casos, pero no aprobó el envío (verifiqué un archivo de salida de 225 casos completo), así que supongo que tiene algunos problemas y estoy bastante seguro de que hay mejores soluciones.
Algoritmo
Primero definamos N , el número de celdas no minadas:
N = R * C - M
Una solución simple es llenar un área de N células no minadas línea por línea de arriba a abajo. Ejemplo para R=5 , C=5 , M=12 :
c....
.....
...**
*****
*****
Es decir:
- Siempre comienza en la esquina superior izquierda.
- Rellene las filas
N / Ccon minas que no sean de arriba a abajo. - Llene la siguiente línea con
N % Csin minas de izquierda a derecha. - Rellena el resto con minas.
Solo hay unos pocos casos especiales de los que hay que preocuparse.
Solo no mio
Si N=1 , cualquier configuración es una solución correcta.
Una sola fila o una sola columna
Si R=1 , simplemente complete las N minas que no son de izquierda a derecha. Si C=1 , llene N filas con un (solo) no mío.
Muy pocos no-minas
Si N es par, debe ser> = 4.
Si N es impar, debe ser> = 9. Además, R y C deben ser> = 3.
De lo contrario no hay solución.
No puede llenar las primeras dos filas
Si N es par y no puede llenar al menos dos filas con minas que no son minas, entonces llene las dos primeras filas con N / 2 no sean minas.
Si N es impar y no puede llenar al menos dos filas con no-minas y una tercera fila con 3 no-minas, entonces llene las primeras dos filas con (N - 3) / 2 no-minas y la tercera fila con 3 no minas.
Único no mío en la última fila.
Si N % C = 1 , mueva la última no mina de la última fila completa a la siguiente fila.
Ejemplo para R=5 , C=5 , M=9 :
c....
.....
....*
..***
*****
Resumen
Es posible escribir un algoritmo que implemente estas reglas y devuelva una descripción del campo de mina resultante en O(1) . Dibujar la cuadrícula toma O(R*C) , por supuesto. También escribí una implementación en Perl basada en estas ideas que fue aceptada por el Juez de Jam de Código.
Código z autoexplicativo con comentarios. O (r + c)
import java.util.Scanner;
public class Minesweeper {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int j=0;j<n;j++) {
int r =sc.nextInt(),
c = sc.nextInt(),
m=sc.nextInt();
//handling for only one space.
if(r*c-m==1) {
System.out.println("Case #"+(int)(j+1)+":");
String a[][] = new String[r][c];
completeFill(a,r-1,c-1,"*");
printAll(a, r-1, c-1);
}
//handling for 2 rows or cols if num of mines - r*c < 2 not possible.
//missed here the handling of one mine.
else if(r<2||c<2) {
if(((r*c) - m) <2) {
System.out.println("Case #"+(int)(j+1)+":");
System.out.println("Impossible");
}
else {
System.out.println("Case #"+(int)(j+1)+":");
draw(r,c,m);
}
}
//for all remaining cases r*c - <4 as the click box needs to be zero to propagate
else if(((r*c) - m) <4) {
System.out.println("Case #"+(int)(j+1)+":");
System.out.println("Impossible");
}
//edge cases found during execution.
//row or col =2 and m=1 then not possible.
//row==3 and col==3 and m==2 not possible.
else {
System.out.println("Case #"+(int)(j+1)+":");
if(r==3&&m==2&&c==3|| r==2&&m==1 || c==2&&m==1) {
System.out.println("Impossible");
}
else {
draw(r,c,m);
}
}
}
}
/*ALGO : IF m < (r and c) then reduce r or c which ever z max
* by two first time then on reduce by factor 1.
* Then give the input to filling (squarefill) function which files max one line
* with given input. and returns the vals of remaining rows and cols.
* checking the r,c==2 and r,c==3 edge cases.
**/
public static void draw(int r,int c, int m) {
String a[][] = new String[r][c];
int norow=r-1,nocol=c-1;
completeFill(a,norow,nocol,".");
int startR=0,startC=0;
int red = 2;
norow = r;
nocol = c;
int row=r,col=c;
boolean first = true;
boolean print =true;
while(m>0&&norow>0&&nocol>0) {
if(m<norow&&m<nocol) {
if(norow>nocol) {
norow=norow-red;
//startR = startR + red;
}
else if(norow<nocol){
nocol=nocol-red;
//startC = startC + red;
}
else {
if(r>c) {
norow=norow-red;
}
else {
nocol=nocol-red;
}
}
red=1;
}
else {
int[] temp = squareFill(a, norow, nocol, startR, startC, m,row,col,first);
norow = temp[0];
nocol = temp[1];
startR =r- temp[0];
startC =c -temp[1];
row = temp[3];
col = temp[4];
m = temp[2];
red=2;
//System.out.println(norow + " "+ nocol+ " "+m);
if(norow==3&&nocol==3&&m==2 || norow==2&&m==1 || nocol==2&&m==1) {
print =false;
System.out.println("Impossible");
break;
}
}
first = false;
}
//rectFill(a, 1, r, 1, c);
if(print)
printAll(a, r-1, c-1);
}
public static void completeFill(String[][] a,int row,int col,String x) {
for(int i=0;i<=row;i++) {
for(int j=0;j<=col;j++) {
a[i][j] = x;
}
}
a[row][col] = "c";
}
public static void printAll(String[][] a,int row,int col) {
for(int i=0;i<=row;i++) {
for(int j=0;j<=col;j++) {
System.out.print(a[i][j]);
}
System.out.println();
}
}
public static int[] squareFill(String[][] a,int norow,int nocol,int startR,int startC,int m,int r, int c, boolean first) {
if(norow < nocol) {
int fil = 1;
m = m - norow;
for(int i=startR;i<startR+norow;i++) {
for(int j=startC;j<startC+fil;j++) {
a[i][j] = "*";
}
}
nocol= nocol-fil;
c = nocol;
norow = r;
}
else {
int fil = 1;
m = m-nocol;
for(int i=startR;i<startR+fil;i++) {
for(int j=startC;j<startC+nocol;j++) {
a[i][j] = "*";
}
}
norow = norow-fil;
r= norow;
nocol = c;
}
return new int[] {norow,nocol,m,r,c};
}
}
Este es mi code . Resolví tomando diferentes casos como si el number of rows=1 o el number of columns=1 o si el number of mines=(r*c)-1 y algunos otros casos.
La posición en el diseño para hacer clic se coloca en a[r-1][c-1] (''0'' indexado) cada vez.
Para esta pregunta había dado pocos intentos equivocados y cada vez encontraba un nuevo caso. Eliminé algunos casos en los que la solución no es posible utilizando goto y dejé que salte para terminar donde se imprime de forma imposible. Una solución muy simple (De hecho, se puede decir una solución de fuerza bruta ya que codifiqué para diferentes casos posibles individualmente). Este es un editorial para mi código. Y en github .
Hay una solución más general a este problema que pasa los casos de prueba pequeños y grandes. Evita tener que pensar en todos los casos especiales, no importa cuáles son las dimensiones de la placa y no requiere ningún seguimiento.
ALGORITMO
La idea básica es comenzar con una cuadrícula llena de minas y eliminarlas a partir de la celda {0, 0} hasta que haya el número correcto de minas en el tablero.
Obviamente, debe haber alguna forma de determinar qué minas eliminar a continuación y cuando sea imposible eliminar la cantidad correcta de minas. Para hacer esto podemos mantener un int[][] que representa el tablero. Cada celda con una mina contiene -1 y aquellas sin minas contienen un número entero que es el número de minas adyacentes a la celda; lo mismo que en el juego real.
También defina el concepto de una "frontera" que es todas las celdas no mineras que no son cero, es decir, aquellas celdas con minas adyacentes.
Por ejemplo la configuración:
c . *
. . *
. . *
* * *
Sería representado como:
0 2 -1
0 3 -1
2 5 -1
-1 -1 -1
Y la frontera contendría las celdas con valores: 2, 3, 5, 2
Al remover las minas la estrategia es:
- Encuentra una celda en la frontera que tenga el mismo valor que el número restante de minas que eliminar. Entonces, en el ejemplo anterior, si tuviéramos 5 minas más para eliminar, se elegirían las celdas con valor 5 en la frontera.
- En su defecto eligió la célula fronteriza más pequeña. Así que cualquiera de los 2 en el ejemplo anterior.
- Si el valor de la celda elegida es mayor que el número de minas que quedan por eliminar, es imposible construir este tablero, así que devuelva falso.
- Si no, elimina todas las minas que rodean la celda fronteriza elegida.
- Repita hasta que la cantidad correcta de minas esté presente en el tablero; se han cumplido las restricciones del problema.
En java esto se parece a:
// Tries to build a board based on the nMines in the test case
private static boolean buildBoard(TestCase t) throws Exception {
if (t.nMines >= t.Board.rows() * t.Board.cols()) {
return false;
}
// Have to remove the cell at 0,0 as the click will go there
t.Board.removeMine(0, 0);
while (!t.boardComplete()) {
Cell c = nextCell(t);
// If the value of this cell is greater than what we need to remove we can''t build a board
if (t.Board.getCell(c.getRow(), c.getCol()) > t.removalsLeft()) {
return false;
}
t.Board.removeNeighbourMines(c.getRow(), c.getCol());
}
return true;
}
// Find frontier cell matching removals left, else pick the smallest valued cell to keep things balanced
private static Cell nextCell(TestCase t) {
Cell minCell = null;
int minVal = Integer.MAX_VALUE;
for (Cell c : t.Board.getFrontier()) {
int cellVal = t.Board.getCell(c.getRow(), c.getCol());
if (cellVal == t.removalsLeft()) {
return c;
}
if (cellVal < minVal) {
minVal = cellVal;
minCell = c;
}
}
if (minCell == null) {
throw new NullPointerException("The min cell wasn''t set");
}
return minCell;
}
PRUEBA / INTUICIÓN
En primer lugar, un tablero se define como válido si se puede resolver con un solo clic, incluso si solo hay una celda en el tablero donde puede ocurrir este clic. Por lo tanto, para que una placa sea válida, todas las celdas no minadas deben ser adyacentes a una celda con valor 0, si este no es el caso, la celda se define como inalcanzable . Esto se debe a que sabemos con certeza que todas las celdas adyacentes a una celda 0 no son minas, por lo que pueden revelarse de manera segura y el juego lo hará automáticamente para el jugador.
Un punto clave para probar este algoritmo es que siempre es necesario eliminar todas las minas que rodean la celda fronteriza más pequeña para mantener el tablero en un estado válido . Esto es bastante fácil de probar simplemente dibujando un tablero (como el de arriba) y seleccionando la celda de valor más bajo (en este caso, la parte superior derecha 2). Si solo se elimina una sola mina, entonces la junta no sería válida, estaría en cualquiera de estos dos estados:
0 1 1
0 2 -1
2 5 -1
-1 -1 -1
o
0 1 -1
0 2 2
2 5 -1
-1 -1 -1
que ambos tienen células inalcanzables .
Por lo tanto, ahora es cierto que siempre la elección de la celda fronteriza más pequeña mantendrá al tablero en un estado válido y mi primer instinto fue que continuar eligiendo estas celdas atravesaría todos los estados válidos, sin embargo, esto no es correcto. Esto se puede ilustrar con un caso de prueba como 4 4 7 (por lo que hay 9 celdas que no son minas). Entonces considere la siguiente tabla:
0 2 -1 -1
2 5 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
Si continúa eligiendo la celda fronteriza más pequeña, el algoritmo puede hacer lo siguiente:
0 2 -1 -1
0 3 -1 -1
0 3 -1 -1
0 2 -1 -1
Lo que significa que ahora es imposible eliminar solo una mina para completar el tablero para este caso. Sin embargo, la elección de una celda fronteriza que coincida con el número de minas restantes (si existe) garantiza que se hayan elegido las 5, lo que resultaría en un cuadrado de 3x3 de no minas y una solución correcta para el caso de prueba.
En este punto, decidí probar el algoritmo en todos los casos de prueba en el siguiente rango:
0 < R < 20
0 < C < 20
0 ≤ M < R * C
y descubrió que logró identificar correctamente todas las configuraciones imposibles y construir soluciones que parecían razonables a las configuraciones posibles.
La intuición adicional detrás de por qué elegir la celda fronteriza con el mismo valor que el número restante de minas (si existiera) es correcta es que permite que el algoritmo encuentre configuraciones para soluciones que requieren un número impar de minas que no son minas.
Cuando implementé originalmente este algoritmo, tenía la intención de escribir heurísticas que construyeran el área no minada en un arreglo cuadrado. Teniendo en cuenta de nuevo el caso de prueba 4 4 7 , terminaría haciendo esto:
0 0 2 -1
0 1 4 -1
2 4 -1 -1
-1 -1 -1 -1
observe cómo ahora tenemos un 1 en la frontera que aseguraría que la celda final eliminada completara el cuadrado para dar:
c . . *
. . . *
. . . *
* * * *
Esto significaría que las heurísticas cambian ligeramente a:
- Elige la celda fronteriza más pequeña.
- En el caso de un empate, elija la primera celda agregada a la lista de la frontera
Esto podría implementarse manteniendo una cola FIFO de celdas fronterizas, pero rápidamente me di cuenta de que es más complicado de lo que parece. Esto se debe al hecho de que los valores de las celdas fronterizas son interdependientes y, por lo tanto, se debe tener cuidado para mantener la colección de celdas fronterizas en el estado correcto y también para no utilizar el valor de las celdas en cualquier tipo de valor hash, etc. Estoy seguro de que esto se podría hacer, pero al darse cuenta de que solo agregar la heurística adicional para seleccionar las celdas con valores iguales a los remociones restantes funcionó, parece que este fue el enfoque más fácil.
La solución se puede encontrar here . Contenidos de la página de abajo.
Hay muchas formas de generar una configuración de mina válida. En este análisis, tratamos de enumerar todos los casos posibles e intentar generar una configuración válida para cada caso (si existe). Más tarde, después de tener una idea, proporcionamos un algoritmo más fácil de implementar para generar una configuración de mina válida (si existe).
Enumerar todos los casos posibles.
Comenzamos revisando los casos triviales:
Si solo hay una celda vacía, entonces podemos llenar todas las celdas con minas, excepto la celda donde hace clic. Si R = 1 o C = 1, las minas se pueden colocar de izquierda a derecha o de arriba a abajo respectivamente y hacer clic en la celda más a la derecha o más abajo, respectivamente. Si el tablero no está en los dos casos triviales anteriores, significa que el tablero tiene al menos 2 x 2 tamaños. Entonces, podemos verificar manualmente que:
Si el número de celdas vacías es 2 o 3, es imposible tener una configuración válida. Si R = 2 o C = 2, las configuraciones válidas existen solo si M es par. Por ejemplo, si R = 2, C = 7 y M = 5, es imposible ya que M es impar. Sin embargo, si M = 6, podemos colocar las minas en la parte izquierda del tablero y hacer clic en la parte inferior derecha, así: * .... * ... c Si el tablero no está en ninguno de los casos anteriores , significa que el tablero es de al menos 3 x 3 de tamaño. En este caso, siempre podemos encontrar una configuración de mina válida si el número de celdas vacías es mayor que 9. Esta es una forma de hacerlo:
Si el número de celdas vacías es igual o mayor que 3 * C, entonces las minas se pueden colocar fila por fila desde arriba hacia abajo. Si el número de minas restantes puede llenar completamente la fila o es menor que C - 2, coloque las minas de izquierda a derecha en esa fila. De lo contrario, el número de minas restantes es exactamente C - 1, coloque la última mina en la siguiente fila. Por ejemplo: ****** ****** *****. **** .. ...... -> * ..... ...... ...... ..... c ..... c Si el número de celdas vacías es menor que 3 * C pero al menos 9, primero llenamos todas las filas con minas, excepto las últimas 3 filas. Para las últimas 3 filas, llenamos las columnas restantes columna por columna desde la columna más a la izquierda. Si las minas restantes en la última columna son dos, entonces la última mina se debe colocar en la siguiente columna. Por ejemplo: ****** ****** .... -> * ... ** .... * ..... * .... c * .... c Ahora , nos quedan como máximo 9 celdas vacías que se encuentran en las celdas cuadradas de 3 x 3 en la esquina inferior derecha. En este caso, podemos verificar a mano que si el número de celdas vacías es 5 o 7, es imposible tener una configuración de mina válida. De lo contrario, podemos codificar una configuración válida para cada número de celdas vacías en esas 3 x 3 celdas cuadradas.
Suspiro ... eso fue un montón de casos para cubrir! ¿Cómo nos convencemos a nosotros mismos de que cuando codificamos la solución, no perdemos ningún caso de esquina?
Enfoque de fuerza bruta
Para la entrada pequeña, el tamaño de la placa es a lo sumo 5 x 5. Podemos verificar todas las configuraciones posibles de la mina (25 elegir M) y encontrar una que sea válida (es decir, al hacer clic en una celda vacía en la configuración revelar todas las demás celdas vacías). Para verificar si una configuración de mina es válida, podemos ejecutar un algoritmo de relleno de inundación (o una simple búsqueda sin aliento) desde la celda vacía en la que se hizo clic y verificar que todas las demás celdas vacías son accesibles (es decir, están en un componente conectado) . Tenga en cuenta que también debemos comprobar todas las posiciones de clic posibles. Este enfoque de fuerza bruta es lo suficientemente rápido para la pequeña entrada.
El enfoque de fuerza bruta se puede usar para verificar (para valores pequeños de R, C, M) si hay un falso negativo en nuestra estrategia de enumeración anterior. Se encuentra un falso negativo cuando existe una configuración de mina válida, pero la estrategia de enumeración anterior da como resultado Imposible. Una vez que confiamos en que nuestra estrategia de enumeración no produce ningún falso negativo, podemos usarla para resolver la gran información.
Un enfoque más fácil de implementar
Después de jugar con varias configuraciones de minas válidas utilizando la estrategia de enumeración anterior, puede observar un patrón: en una configuración de minas válida, el número de minas en una fila en particular es siempre igual o mayor que el número de minas de las filas que se encuentran debajo y Todas las minas están alineadas a la izquierda en una fila. Con esta información, podemos implementar un algoritmo de retroceso más simple que coloca las minas fila por fila de arriba a abajo con un número no creciente de minas a medida que procedemos a completar la siguiente fila y podar si la configuración de la fila actual no es válida ( se puede comprobar haciendo clic en la celda inferior derecha). Este retroceso con la poda puede manejar hasta 50 x 50 tablas de tamaño en un tiempo razonable y es más fácil de implementar (es decir, no es necesario enumerar los casos difíciles).
Si el tiempo del concurso fuera más corto, es posible que no tengamos tiempo suficiente para enumerar todos los casos posibles.En este caso, puede ser una buena idea apostar por el algoritmo de seguimiento (o cualquier otro algoritmo que sea más fácil de implementar). Encontrar tales algoritmos es un arte :).
Mi enfoque a este problema fue el siguiente:
- Para una cuadrícula de 1x1, M tiene que ser cero, de lo contrario es imposible
- Para una cuadrícula Rx1 o 1xC, necesitamos M <= R * C - 2 (coloque ''c'' en la última celda con una celda vacía al lado)
- Para una cuadrícula RxC, necesitamos M <= R * C - 4 (coloque ''c'' en una esquina con 3 celdas vacías a su alrededor)
En resumen, c siempre tendrá celdas que no sean de minas al lado, sin importar qué, de lo contrario es imposible. Esta solución tiene sentido para mí, y he comprobado la salida contra su muestra y sus pequeñas entradas, sin embargo, no fue aceptada.
Aquí está mi código:
import sys
fname = sys.argv[1]
handler = open(fname, "r")
lines = [line.strip() for line in handler]
testcases_count = int(lines.pop(0))
def generate_config(R, C, M):
mines = M
config = []
for row in range(1, R+1):
if mines >= C:
if row >= R - 1:
config.append(''''.join([''*'' * (C - 2), ''.'' * 2]))
mines = mines - C + 2
else:
config.append(''''.join(''*'' * C))
mines = mines - C
elif mines > 0:
if row == R - 1 and mines >= C - 2:
partial_mines = min(mines, C - 2)
config.append(''''.join([''*'' * partial_mines, ''.'' * (C - partial_mines)]))
mines = mines - partial_mines
else:
config.append(''''.join([''*'' * mines, ''.'' * (C - mines)]))
mines = 0
else:
config.append(''''.join(''.'' * C))
# click the last empty cell
config[-1] = ''''.join([config[-1][:-1], ''c''])
return config
for case in range(testcases_count):
R, C, M = map(int, lines.pop(0).split('' ''))
# for a 1x1 grid, M has to be zero
# for a Rx1 or 1xC grid, we must have M <= # of cells - 2
# for others, we need at least 4 empty cells
config_possible = (R == 1 and C == 1 and M==0) or ((R == 1 or C == 1) and M <= R * C - 2) or (R > 1 and C > 1 and M <= R * C - 4)
config = generate_config(R, C, M) if config_possible else None
print "Case #%d:" % (case+1)
if config:
for line in config: print line
else:
print "Impossible"
handler.close()
Funcionó bastante bien contra su muestra en el sitio web y contra la pequeña información que proporcionaron, pero parece que me estoy perdiendo algo.
Aquí está la salida a la muestra:
Case #1:
Impossible
Case #2:
*
.
c
Case #3:
Impossible
Case #4:
***....
.......
.......
......c
Case #5:
**********
**********
**********
**********
**********
**********
**********
**********
**........
.........c
Actualización: Leyendo el editorial de vinaykumar, entiendo lo que está mal con mi solución. Reglas básicas del buscaminas que debería haber cubierto, bastante.
Mi estrategia era muy similar a la tuya y pasé tanto en grande como en pequeña. ¿Pensaste en los casos de abajo?
R * C - M = 1
Solo hay una fila
Sólo hay dos filas
Di la vuelta a R y C cuando R> C.
Separé esto en dos casos especiales iniciales, luego tuve un algoritmo general. La versión tl; dr es para construir un cuadrado de espacios en blanco desde la parte superior izquierda. Similar a otras respuestas, pero con menos casos especiales.
Casos especiales
Caso 1
Sólo 1 espacio en blanco. Simplemente haga clic en la esquina superior izquierda y termine.
Caso 2
2 o 3 espacios en blanco, con una cuadrícula que no es Rx1 o 1xC. Esto es imposible, así que fallamos temprano.
Algoritmo
Siempre haga clic en la esquina superior izquierda. Comience con un cuadrado en blanco de 2x2 en la parte superior izquierda (tenemos al menos 4 espacios en blanco). Ahora tenemos que añadir los espacios en blanco restantes. Luego expandimos el cuadrado a lo largo de un borde y luego del otro, hasta que no tenemos más espacios en blanco.
Ejemplo de orden de supresión:
C 2 6 12
1 3 7 13
4 5 8 14
9 10 11 15
Caso imposible
Tenga en cuenta que al comenzar un nuevo borde, debemos colocar al menos dos espacios en blanco para que esto sea válido. Entonces, si solo tenemos un espacio en blanco para colocar, entonces esto debe ser inválido (a menos que nuestro borde tenga la longitud uno). Mi lógica se veía así:
if maxEdgeLength > 1 and remainingBlanks == 1:
print(''Impossible'')
return
Sin embargo, podríamos haber dejado fuera el final del último borde, lo que nos daría dos espacios en blanco ahora. Por supuesto, solo podemos dejar el último espacio en blanco si el último borde tenía más de 2 espacios en blanco.
Mi lógica para este caso especial se veía así:
if remainingBlanks == 1 and lastEdgeSize > 2:
mineMatrix[lastBlank] = ''*''
blanks += 1
También probé suerte en esta pregunta, pero por alguna razón no pasé los cheques.
Pensé que es solucionable para (matriz 3x3) si hay menos de (filas * cols-4) minas, ya que solo necesitaba 4 celdas para "c" y sus límites como "."
Mis algoritmos siguen:
¿Soluble? :
- Comprueba si hay suficiente espacio para las minas (
rows*cols - 4 == maximum mines) - Excepciones como filas == 1, cols == 1; entonces son filas * cols-2
- Condicional si es posible o imposible
Construir solución
- Construye
rows*cols matrix, con valor predeterminado nil - Vaya a
m[0][0]y asigne''c'' - Defina
m[0][0]alrededores con''.'' - Recorra la parte inferior derecha de Matrix y asigne
''*''hasta que las minas hayan terminado, luego asigne''.''
Utilicé la búsqueda con retroceso, pero solo pude resolver la pequeña entrada.
Básicamente, el algoritmo comienza con el tablero lleno de minas e intenta eliminar las minas de manera que el primer "clic" resuelva el tablero. El problema es que para permitir que un "clic" se expanda a otra celda, la expansión provendrá de otra celda que debe tener todas las demás celdas vecinas borradas también. A veces, para expandirte a otra celda, deberías eliminar otras minas y terminar con menos minas de las necesarias. El algoritmo retrocederá si alcanza tal posición.
Tal vez sea más sencillo hacer lo contrario. Comience con un tablero vacío y agregue cada mina de manera que no impida la "expansión" del clic inicial.
El código completo de Python está abajo:
directions = [
[-1, -1], [-1, 0], [-1, 1],
[0, -1], [0, 1],
[1, -1], [1, 0], [1, 1],
]
def solve(R, C, M):
def neighbors(i, j):
for di, dj in directions:
if 0 <= (i + di) < R and 0 <= (j + dj) < C:
yield (i + di, j + dj)
def neighbors_to_clear(i, j, board):
return [(ni, nj) for ni, nj in neighbors(i, j) if board[ni][nj] == "*"]
def clear_board(order):
to_clear = R * C - M - 1
board = [["*" for _ in range(C)] for _ in range(R)]
for i, j in order:
board[i][j] = "."
for ni, nj in neighbors_to_clear(i, j, board):
to_clear -= 1
board[ni][nj] = "."
return board, to_clear
def search(ci, cj):
nodes = []
board = []
to_clear = 1
nodes.append((ci, cj, []))
while nodes and to_clear > 0:
i, j, order = nodes.pop()
board, to_clear = clear_board(order)
neworder = order + [(i, j)]
if to_clear == 0:
board[ci][cj] = "c"
return board
elif to_clear > 0:
for ni, nj in neighbors_to_clear(i, j, board):
board[ni][nj] = "."
nodes.append([ni, nj, neworder])
for i in range(R):
for j in range(C):
board = search(i, j)
if board:
for row in board:
print "".join(row)
return
print "Impossible"
return
T = int(raw_input())
for i in range(1, T + 1):
R, C, M = map(int, raw_input().split(" "))
print("Case #%d:" % i)
solve(R, C, M)