Number Board Jump

Interview

Time limit2sMemory limit128 MB

Summary
Count the distinct length-6 digit strings obtainable by starting anywhere on a 5x5 digit board and making five moves to adjacent cells.
Level

Medium4 of 10

Topics
DFS, Brute force, Backtracking
Solved
No attempts yet

Problem

There is a 5×5 number board. Each cell contains one digit from 0 to 9.

Choose any cell as the starting position, then move exactly five times to an adjacent cell in one of the four cardinal directions. Concatenating the digit in the starting cell and the five digits visited during the moves creates a string of length 6.

A path may visit the same cell more than once. A result that starts with 0 is still counted as a distinct string of length 6.

Given the board, determine how many different strings of length 6 can be made.

Input

Five lines describe the board. Each line contains five integers from 0 to 9 separated by spaces.

Output

Print the number of different strings of length 6 that can be made.

Hint

For instance, on a board where every cell is 1 except for a single 2, the possible strings are 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, and 212121.

Examples1

  1. Example 1

    Input
    1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1
    Expected output
    15