Astral Superposition

Análisis oficial (C++, Python) 

Explicación

Caso 1: $A = 0$ y $B = 0$

Como ninguna estrella se mueve, solo pueden desaparecer en la imagen 2.

• B significa que la estrella permaneció en ambas imágenes
• G significa que la estrella existió solo en la primera imagen, y luego desapareció en la segunda imagen.
• W significa que en ninguna de las dos fotos había una estrella. Para contar cuántas estrellas había en la imagen 2, contamos cuántas B y G hay.

Para el caso anterior con $A = 0$ y $B = 0$ la respuesta sería $7$ estrellas.

Caso 2: $A \ne 0$ o $B \ne 0$

Esto empezará con algo de lógica simple y se extenderá más adelante (para las estrellas B).

Cuando $A$ y $B$ son distintos de cero podemos decir que la estrella $(i, j)$ se movió a la estrella $(i+A, j+B)$.

Así, para cada estrella (de arriba-izquierda a abajo-derecha) $(i, j)$, si hay una $(i+A, j+B)$ presente, podemos decir que $(i+A, j+B)$ fue desplazada y pertenece a la imagen 2.

Por ejemplo, cuando $A = 1$ y $B = 2$, sabemos que la estrella en $(1, 1)$ se movió a $(2, 3)$.

Todas las estrellas desplazadas son:

• $(1,1)$ a $(2,3)$
• $(3,1)$ a $(4,3)$
• $(2,3)$ a $(3,5)$ y son de la imagen 2, así que al quitar las estrellas que sabemos que están en la imagen 2 obtenemos un mínimo de $4$ estrellas.

No asignamos las estrellas B como solo-imagen-2 porque están en ambas imágenes.

Casos borde

Muchos casos borde vienen de las celdas B, por ejemplo con $A = 1$ y $B = 1$

resultaría en $-1$ porque si retrocedemos, una celda W apunta a B, lo cual no es posible para que esté en ambas imágenes.

Otro caso con $A=1$ y $B=0$ es

con la lógica anterior podemos apuntar

• $(1,1)$ a $(2,1)$
• $(1,2)$ a $(2,2)$ ¡lo cual es incorrecto!

Esto se debe a que la celda B tiene que ser apuntada por algo. Esto significa que el $(2,1)$ de la imagen 2 fue borrado, y en realidad es de la imagen 1.

Algoritmo

Estas son todas las reglas base, así que ahora podemos estructurar la lógica:

• Si $A=0$ y $B=0$ entonces contar cuántas G y B ocurren.
• En caso contrario, para cada estrella no asignada a la imagen 2, sumar $A$ y $B$ a sus coordenadas y ver a dónde lleva.
• Si lleva a una estrella (que no sea B) entonces asignarla a la imagen 2.
• Para cada celda B, comprobar si otra estrella lleva a ella; en caso contrario devolver $-1$.
• Si una celda B es alcanzada por una estrella asignada a la imagen 2, hay que desasignarla de la imagen 2.

Implementación

Complejidad temporal: $\mathcal{O}(T\cdot N^2)$

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, a, b;
		cin >> n >> a >> b;
 
		vector<string> superimposed(n);
		for (int i = 0; i < n; i++) cin >> superimposed[i];
 
		int allStars = 0;
		for (int x = 0; x < n; x++)
			for (int y = 0; y < n; y++)
				if (superimposed[x][y] != 'W') allStars++;
 
		int stars = 0;
		if (a == 0 && b == 0) {
			// simplemente devolver cuántas estrellas hay
			stars = allStars;
		} else {
			// Primera pasada: ignorar todas las estrellas "dirigidas"
			vector<vector<bool>> image2(n, vector<bool>(n));
 
			for (int x = 0; x < n; x++)
				for (int y = 0; y < n; y++) {
					if (superimposed[y][x] == 'W' || image2[x][y]) continue;
 
					int nx = x + a;
					int ny = y + b;
 
					// en caso contrario ha sido borrada
					if (ny < n && nx < n && superimposed[ny][nx] != 'W') {
						// no ignorar las celdas B
						if (superimposed[ny][nx] != 'B') image2[nx][ny] = true;
					}
				}
 
			/* Segunda pasada, manejar todas las estrellas negras */
			bool invalid = false;
			for (int x = 0; x < n; x++)
				for (int y = 0; y < n; y++) {
					if (superimposed[y][x] != 'B') continue;
 
					int nx = x - a;
					int ny = y - b;
 
					// No es posible que nada haya llevado a esto
					if (nx < 0 || ny < 0 || superimposed[ny][nx] == 'W') {
						invalid = true;
						break;
					}
 
					// quien nos llevó no pudo haber sido image2, fue
					// removido
					if (image2[nx][ny]) { image2[nx][ny] = false; }
				}
 
			// Contar cuántas estrellas hay en la imagen 2
			int image2numstars = 0;
			for (int x = 0; x < n; x++)
				for (int y = 0; y < n; y++) { image2numstars += image2[x][y]; }
 
			if (invalid) stars = -1;
			else stars = allStars - image2numstars;
		}
		cout << stars << "\n";
	}
}