AIOC Banner

Problem: Human LCD

Want to try solving this problem? You can submit your code online if you log in or register.


Human LCD

Time Limit: 10 seconds
Memory Limit: 64 MB

You are working hard to make informatics competitions more entertaining to the public, and are organizing this year's olympiad in a big indoor stadium, with a big audience. While all the contestants will try hard to concentrate on solving problems, cheerleaders will cheer as scores appear on giant screens in real time, the olympiad's mascot will throw small gifts to the crowd and guides will perform as a giant human LCD screen.

All this costs more than expected and you had to find an extra sponsor at the last minute. A fast food chain has agreed to pay for the extra costs on the condition that their logo be added to the end of the human LCD routine.

At the end of the existing routine, the guides will be arranged as a nice 2-dimentional grid. Each cell will contain a guide wearing a coloured t-shirt, forming one pixel of the human LCD screen. You are given a description of this grid and the colour of the guide contained in each cell. You are also given a description of the colour that each cell should display to represent the sponsor's logo perfectly.

As you don't have much time to train the guides for this extra move, you want to make it simple: each guide will either not move, or swap their position with one of the guides in the 4 adjacent cells. All swaps happen simultaneously, and no guide may be involved in more than one swap. Note that unlike real human LCDs, the guides cannot change their colour.

Your goal is to find a collection of such swaps, so that the resulting image formed on the grid is as close as possible to the sponsor's logo.

Input

The first line of input will contain two space-separated integers R, C: the number of rows and columns of the grid (1 ≤ R,C ≤ 100).

The following R lines will describe the initial grid as it is shown to the public at the end of the original routine. Each line describes a row of the grid and contains C space-separated integers, the colours of the guides in the cells of that row. All colours are integers between 0 and 9, inclusive.

The following R lines will describe the grid that you are trying to obtain, representing the sponsor's logo. Each line describes a row and contains C space-separated integers, the colours the cells should show to form the sponsor's logo.

See the Scoring section for a breakdown of the marks awarded for different test cases.

Output

Your program must write several lines to standard output. The first line should contain a single integer S, the number of swaps in your solution.

Each of the S following lines will contain four integers: the coordinates (r1, c1) and (r2, c2) of two adjacent guides who will be asked to swap positions. The cell in the top-left corner has coordinates (0, 0).

Sample Input

3 4
1 2 3 4
4 3 2 1
1 1 2 2
4 3 2 4
1 1 1 2
2 3 2 2

Sample Output

4
0 0 1 0
0 1 0 2
1 1 2 1
1 2 1 3

Performing the swaps in the sample output above gives the following grid:

4 3 2 4
1 1 1 2
1 3 2 2

Out of 12 cells, 11 match the sponsor's logo. This is an optimal solution.

Scoring

The score for each input scenario will be calculated based on the number of cells that match the desired logo, as follows:

For example, suppose that the optimal solution has a=100 matching cells and the original input has b=50 matching cells. Then scores would be assigned as follows:

Matching cells (x) 40 50 60 70 80 85 90 95 100
Score (%, rounded) 0 0 0 0 5 12 26 53 100


The judge's solution finds an optimal solution within the time and memory limits.


The following table lists the sizes of the inputs used in the test data.


R C Percentage of marks
1 100 10%
10 10 10%
20 20 10%
100 100 70%

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 26 August 2019,  4:16am AEST