P16010 [CCO 2016 Day 2] O Canada

In this problem, a *grid* is an $N$-by-$N$ array of cells, where each cell is either red or white. Some grids are *similar* to other grids. Grid $A$ is similar to grid $B$ if and only if $A$ can be transformed into $B$ by some sequence of *changes*. A change consists of selecting a $2$-by-$2$ square in the grid and flipping the colour of every cell in the square. (Red cells in the square will become white; white cells in the square will become red.) You are given $G$ grids. Count the number of pairs of grids which are similar. (Formally, number the grids from $1$ to $G$, then count the number of tuples $(i, j)$ such that $1 \le i < j \le G$ and grid $i$ is similar to grid $j$.)

The first line of input contains $N\ (2 \le N \le 10)$, the size of the grids. The second line contains $G\ (2 \le G \le 10\,000)$, the number of grids. The input then consists of $N \cdot G$ lines, where each line contains $N$ characters, where each character is either `R` or `W`, indicating the colour (red or white) for that element in the grid. Moreover, after the first two lines of input, the next $N$ lines describe the first grid, the following $N$ lines describe the second grid, and so on. For $12$ out of the $25$ marks available for this question, $2 \le G \le 10$.

Output the number of pairs of grids which are similar.

There are exactly two grids, and they are similar because the first grid can be transformed into the second grid using one change (selecting the $2$-by-$2$ square consisting of the entire grid).