This page is still under construction.

Parts of this page are still being built. What you see may change.

Rolling the Dice 2

Time limit2sMemory limit1024 MB

Summary
A die rolls across an N by M grid, turning based on its bottom face versus the cell value, and each landing adds the value times the size of its equal-value connected region.
Level

Medium5 of 10

Topics
Simulation, Implementation, BFS, Array
Solved
No attempts yet

Problem

There is a map of size N×M. The right side of the map is east and the top side is north. A coordinate on the map is written as (r, c), where r is the number of cells from the north and c is the number of cells from the west. The top-left cell has coordinate (1, 1), and the bottom-right cell has coordinate (N, M). A die sits on top of this map, and each face of the die has one integer between 1 and 6, inclusive. A face of the die is the same size as a cell of the map, and the net of the die is shown below.

  2
4 1 3
  5
  6

The die is placed on the map with its top face showing 1 and its east-facing side showing 3, and the coordinate of the cell it sits on is (1, 1). Each cell of the map also has one integer written on it. Initially, the die's direction of movement is east. One move of the die works as follows.

  1. The die rolls one cell in its direction of movement. If there is no cell in that direction, the die reverses its direction of movement and then rolls one cell.

  2. The die earns the score of the cell (x, y) it lands on.

  3. The die compares the integer A on its bottom face with the integer B on the cell (x, y) it occupies and decides its direction of movement.

    • If A > B, it rotates its direction of movement 90 degrees clockwise.
    • If A < B, it rotates its direction of movement 90 degrees counterclockwise.
    • If A = B, its direction of movement does not change.

The score of a cell (x, y) is computed as follows. Let B be the integer on (x, y). Find the total number C of cells reachable from (x, y) by moving consecutively in the four cardinal directions. Every reachable cell must contain the integer B. The score is B multiplied by C.

Given the size of the board, the integers on its cells, and the number of moves K of the die, find the sum of the scores earned in all moves.

Samples 1 through 7 use the same map and only increase the number of moves. Sample 8 uses the same map with a very large number of moves.

Input

The first line gives the height N and width M of the map (2 ≤ N, M ≤ 20) and the number of moves K (1 ≤ K ≤ 1,000).

From the second line, N lines give the numbers written on the map from north to south, and each line lists them from west to east. Each number written on a cell of the map is a natural number less than 10.

Output

Print the sum of the scores earned in all moves on the first line.

Examples5

  1. Example 1

    Input
    4 5 1
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5
    Expected output
    4

  2. Example 2

    Input
    4 5 2
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5
    Expected output
    8

  3. Example 3

    Input
    4 5 3
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5
    Expected output
    14

  4. Example 4

    Input
    4 5 4
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5
    Expected output
    18

  5. Example 5

    Input
    4 5 5
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5
    Expected output
    24