### 2016 Canadian Computing Olympiad

## Day 2, Problem 1 - 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 ≤ `i` < `j` ≤ `G` and grid `i` is similar to grid `j`.)

### Input Format

The first line of input contains `N` (2 ≤ `N` ≤ 10), the size of the grids.

The second line contains `G` (2 ≤ `G` ≤ 10 000), the number of grids.

The input then consists of `N`·`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 ≤ `G` ≤ 10.

### Output Format

Output the number of pairs of grids which are similar.

### Sample Input

2 2 RW WR WR RW

### Sample Output

1

### Explanation

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).

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 64M

**Added:** May 14, 2016

**Author:** nullptr

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

pacuon Jun 15, 2016 - 3:23:56 am UTC Incorrect limits?https://cemc.math.uwaterloo.ca/contests/computing/2016/stage%202/day2.pdf

jargonon Jun 15, 2016 - 5:00:21 pm UTC Re: Incorrect limits?