Warning, the subtasks are not in order of difficulty.

Rar wants to impress Jacq the Dinosaur and wants to show her how *good* he is with kids. As such he has invited an **entire** kindergarten to his wedding. Rar also wants to impress Jacq with his computing skills. So, he wants to make **his** kindergarteners compute things.

Rar will arrange the kindergarteners in an `N` × `M` grid. Each cell of the grid will either contain a wall, or a kindergartener. Each kindergartener can choose to raise up an object, or not raise up anything. This is represented by a number that ranges from 0 to 3. The meaning of those numbers are:

- 0: nothing
- 1: apple
- 2: wall (no kindergartener)
- 3: flag

Flags will only be used in subtask 5. Do **not** use it in any other subtask.

Rar will first instruct each kindergartener to raise up a specific object (or nothing), based on the problem he wishes to solve (this will be further elaborated below). In other words, Rar will set the initial configuration of the grid.

Every second, the kindergartener will look around themselves, observe their surroundings and what their fellow friends are holding up, after which Rar will blow a whistle, and every kindergartener will simultaneously raise an object (or show nothing) based on their observations. Their objective is to transform the grid to the answer of the specific case.

Each kindergartener can only see the `X` × `Y` grid surrounding them (`X` and `Y` are odd numbers) as they are very short. Any cells not in the grid is assumed to be a wall, and will contain the value "2".

For example, in this grid:

1 1 1 0

There are 4 kindergarteners, and if `X` = `Y` = 3, these are their views:

2 2 2 2 2 2 2 1 1 1 1 2 2 1 0 1 0 2 2 1 1 1 1 2 2 1 0 1 0 2 2 2 2 2 2 2

In this grid:

1 0 1

There are 3 kindergarteners, and if `X` = 3, `Y` = 5, these are their views:

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 0 1 2 1 0 1 2 1 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Help them complete their task by coding the functions `subtask1`

, `subtask2`

, `subtask3`

, `subtask4`

and `subtask5`

for the respective subtasks. The function will be of the form:

int subtaskX(std::vector< std::vector<int> > grid){ return 0; }

The variable `grid`

will be the `X` × `Y` grid visible by the kindergarteners. `grid[0][0]`

will be the top left cell, and `grid[X-1][0]`

will be the bottom left cell. The value returned will be what that kindergartener will raise up. Do not return a value not in the range of 0-3, such an object does not exist. Also, kindergarteners cannot raise up walls (that would be *mildly* terrifying). Please make sure that this function will return the same value if the function is called multiple times with the same input, otherwise it might give you a "Wrong Answer". Basically, 2 kindergarteners who see the same thing should raise up the same object.

Once the grid is stable (the grid no longer changes after an iteration), the program will terminate and you will be given full credit if the final grid is identical to the answer. The max number of iterations the kindergarteners are allowed to run for is 500 for all subtasks, otherwise the kindergarteners die of exhaustion, and Rar will be deemed to be bad with kids.

For all subtasks, 1 ≤ `N`, `M` ≤ 30

There are `M` numbers, `A _{0}`,

Before: `A` = [3, 4, 1, 0, 2]

0 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1

After: `A` = [4, 3, 2, 1, 0]

1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0

`X`=`Y`= 3- 1 ≤
`N`,`M`≤ 30 - 0 ≤
`A`≤ N_{i}

There are `M` numbers, `A _{0}`,

Before: `A` = [1, 0, 0, 0, 2]

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1

After: `A` = [3, 0, 0, 0, 0]

0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0

`X`=`Y`= 3- 1 ≤
`N`,`M`≤ 30 - 0 ≤
`A`< N_{i} - Sum of
`A`< N._{i}

There are 2 numbers, `A _{0}` and

Before: `A` = [10, 7]

1 0 0 1 1 1 0 1

After: `A` = [3, 0]

0 0 0 0 1 0 1 0

`X`=`Y`= 3- 1 ≤
`N`≤ 30 `M`= 2- 0 ≤
`A`< 2_{i}^{N} `A`_{0}≥ A_{1}

Now, the kindergarteners' eyesights are **upgraded** to a 3 × 5 grid.

There are `M` numbers, `A _{0}`,

Before: `A` = [3, 0, 2, 9]

0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1

After: `A` = [14, 0, 0, 0]

1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0

`X`= 3,`Y`= 5- 1 ≤
`N`,`M`≤ 30 - 0 ≤ sum of
`A`< 2_{i}^{N}

The kindergarteners' eyesights are again **downgraded** to a 3 × 3 grid :(

Rar has created a maze for the kindergarteners. The maze has a property that there is exactly one possible way to reach any blank cell from any other blank cell moving only horizontally or vertically (note that people cannot pass through walls!). This is such a possible grid:

0 2 0 0 0 0 0 2 2 2 0 2

Rar then takes this grid, and adds two flags (labeled 3) on two different blank cells. Rar will be standing at one of the flags, and Jacq at the other. They have to find each other through the maze. To ensure that they do not get lost, the kindergarteners are tasked to raise an apple on the cells that they should not walk over, because *an apple a day keeps the programmers away*.

Before:

3 2 3 0 0 0 0 2 2 2 0 2

After:

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

`X`=`Y`= 3- 1 ≤
`N`,`M`≤ 30

Download the files under attachments. Compile the code with the command:

`g++ grader.cpp rarkids.cpp -o rarkids`

The first line of the input will contain the subtask number.

The second line will contain `N` and `M` separated by a space.

The next `N` lines will contain `M` numbers, the type of the cell. This will be the initial grid given to the kindergarteners.

The next `N` lines will contain `M` numbers, the type of the cell. This is the final grid the kindergarteners should make.

Subtask | Score |
---|---|

1 | 10 |

2 | 15 |

3 | 15 |

4 | 40 |

5 | 20 |

6 | 0 |