CCO '16 P4 - O Canada

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

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

In this problem, a grid is an -by- array of cells, where each cell is either red or white.

Some grids are similar to other grids. Grid is similar to grid if and only if can be transformed into by some sequence of changes. A change consists of selecting a -by- 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 grids. Count the number of pairs of grids which are similar. (Formally, number the grids from to , then count the number of tuples such that and grid is similar to grid .)

Input Specification

The first line of input contains  , the size of the grids. The second line contains  , the number of grids. The input then consists of lines, where each line contains 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 lines describe the first grid, the following lines describe the second grid, and so on.

For 12 out of the 25 marks available for this question, .

Output Specification

Output the number of pairs of grids which are similar.

2
2
RW
WR
WR
RW

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 -by- square consisting of the entire grid).