Es posible hacer el chequeo mucho mas económicamente, tanto en el tamaño del código como en la complejidad del mismo:
- no requiere hacer loops,
- solo requiere hacer un número fijo de adiciones y comparaciones.
- pero requiere mantener 2 arreglos y 2 enteros.
Esto es lo que se asume, o se fabrica:
- Suponemos que la matriz está llena de 0s inicialmente.
- Poner una de las 2 opciones cambia el 0 por 1 y poner la otra opcion cambia el 0 por -1.
La gracia de esto es que se sabe si hay 4 en linea si al sumar una fila el resultado da N o -N, pero NO ES NECESARIO sumar toda la fila (o todas las filas) o toda la columna (o todas las columnas).
- Se mantiene 2 arreglos: suma_fila[N], suma_columna[N], que guardan la suma de cada fila y columna, parten en 0.
- Cada vez que se juega alguna opción se actualiza solo 1 posicion de cada arreglo, y solo se chequea si ese valor cambio a N (o -N). No es posible que OTRA FILA haya hecho gato si estoy jugando en una.
- La diagonal o contradiagonal solo son 1 entero, tambien parten en 0.
Finalmente el codigo podria ser algo asi (podria tener errores menores)
Código C++:
Ver originalbool hayGato( int fila, int columna, int jugada ) { // "jugada" es 1 o -1
suma_fila[fila] += jugada;
suma_columna[columna] += jugada;
if( fila == columna ) suma_diagonal += jugada;
if( fila + columna == N-1 ) suma_antidiagonal += jugada;
return abs( suma_fila
[fila
] ) == N
|| abs( suma_columna
[columna
] ) == N
|| abs(suma_diagonal
) == N
|| abs(suma_antidiagonal
) == N
; }
Ahi está: El chequeo en menos de 10 líneas, sin loops