Choque de Cultura

Esse problema foi inspirado pelo jogo brasileiro print-and-play "Crop Rotation" (https://boardgamegeek.com/boardgame/219661/crop-rotation).

A ideia principal é implementar uma função de hashing para identificar uma matriz de $$$3 \times 3$$$ espaços. Uma função possível é dada pelo polinômio

$$$h(m) = m_{00} + 4m_{01} + 4^2m_{02} + 4^3m_{10} + 4^4m_{11} + 4^5m_{12} + 4^6m_{20} + 4^7m_{21} + 4^8m_{22}.$$$

Que produz valores no intervalo $$$[0, 4^9 = 262144)$$$. Então, criamos um vetor com esse tamanho que cabe tranquilamente no limite de memória, e atribuímos a ele a função de contar cada padrão $$$3 \times 3$$$ no tabuleiro original. Isso possui complexidade $$$O(nm)$$$, e pelo menos uma constante de $$$9$$$.

Para respondermos cada consulta, verificamos a quantidade de espaços vazios, pois precisaremos pensar em todas as combinações possíveis. No pior caso, precisaremos calcular $$$4^8$$$ combinações diferentes, quando no padrão estiver presente apenas um legume (é possível otimizar essa consulta em específico, mas $$$4^7$$$ é de ordem similar de grandeza então nem vale a pena).

Também é necessário verificar as $$$4$$$ rotações possíveis. Para evitar recontagem, primeiro "uniformizamos" o padrão colocando todos os elementos no topo esquerdo, e em seguida o rotacionamos (utilizo um método fazendo $$$6$$$ trocas na matriz). Então, verificamos se já contamos aquele padrão utilizando um set.

Esse algoritmo passa no tempo limite, mas realmente é uma problema meio caótico devido as constantes envolvidas.