CCO '16 P4 - O Canada

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 1G

Problem type
Canadian Computing Olympiad: 2016 Day 2, Problem 1

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

Input Specification

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 Specification

Output the number of pairs of grids which are similar.

Sample Input


Sample Output



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


There are no comments at the moment.