[Super Básica] Introducción a la resolución de problemas en TopCoder

Hace unos meses, empecé a ayudar a unos amigos (entre ellos, [follow them on twitter!] @hpmaxi, @fern17, y @escudero89) a meterse en la resolución de problemas de algoritmia.

El primer problema que usé fué uno muy fácil, sacado del archivo de problemas de topcoder. Se llamaba WhiteCells y pueden ver el enunciado original en la web de TopCoder.

Traduje el problema para hacer la cosa más light:

Definición del problema: WhiteCells

Un tablero de ajedrez es una grilla de 8×8 celdas. En cada columna y cada fila, las celdas se alternan entre blanco y negro. La celda de arriba a la izquierda (0, 0) es blanca. Se dá como dato un tablero en forma de vector, donde el j-avo caracter del i-avo elemento es ‘F’ si la celda en la j-ava columna desde la izquierda e i-ava fila desde arriba está ocupado, o ‘.’ si está vacío. Se debe crear una clase WhiteCells con el método countOccupied, que debe devolver el numero total de celdas blancas ocupadas en el tablero.

Definición

Clase: WhiteCells
Método: countOccupied
Parámetros: vector
Valor de retorno: int
‘Firma’ del método: int countOccupied(vector board)
(asegurarse de que el método sea público)

Limites
- ‘board’ contendrá exactamente 8 elementos.
- Cada elemento de ‘board’ contendrá exactamente 8 caracteres.
- ‘board’ sólo contendrá caracteres que sean ‘F’ o ‘.’.

¿Como encaramos un problema así?

Primero nos fijamos en la entrada. Un vector de strings. Podría haber sido simplemente un vector< vector >, pero bueno.
¿Cuál es el principal problema? “iterar” a través de todas las casillas. Eso lo hacemos simplemente con 2 bucles “for”.
¿Qué obstáculos se presentan? Solamente uno: saber si las casillas son blancas o negras. Esto requiere media neurona más.

Estrategia

Simplifiquemos el problema. Supongamos que tenemos un tablero de tan solo 4 casillas. La casilla de arriba a la izquierda es blanca, según dice el problema. La segunda para la derecha es negra. La de abajo de la primera casilla es negra también. La que nos queda, la de más abajo a la derecha, es negra.

Si escribimos esto en coordenadas X, Y tenemos:
{0,0} = Blanca
{1,0} = Negra
{0,1} = Negra
{1,1} = Blanca
Acá es donde debe intervenir una divinidad (¿le tengo que pedir el cartel de sarcasm a Sheldon?) para darnos cuenta que si sumamos la coordenada X e Y, y dividimos por dos, obtenemos un resto que puede ser 0 o 1. Si es cero el resto, estamos frente a una casilla blanca. Si es 1, es una casilla negra.

Resolución

Pseudo-Codigo

contador = 0
para cada i desde 0 a 7 inclusive
   para cada j desde 0 a 7 inclusive
      si (i+j) % 2 = 0 // Es una casilla blanca, de las que nos interesan
         si board[i][j] = 'F'
            contador++
retornar contador

Implementación en C++