Pipe Move 2

Interview

Time limit0.5sMemory limit512 MB

Summary
Count the ways to push a 2-cell pipe (horizontal, vertical, or diagonal) across an N by N grid so its end reaches (N, N), keeping all covered cells empty.
Level

Medium5 of 10

Topics
Dynamic programming, Implementation, Simulation, Matrix
Solved
No attempts yet

Problem

Yuhyeon has moved into a new house. The house can be represented as an N×N grid, divided into 1×1 square cells. Each cell is denoted by (r, c), where r is the row number and c is the column number, and row and column numbers start at 1. Each cell is either empty or a wall.

Today, to repair the house, he wants to move a single pipe. The pipe has the shape shown below and occupies 2 consecutive cells.

The pipe can be rotated, and there are 3 possible orientations as shown below.

The pipe is very heavy, so Yuhyeon wants to move it by pushing it. Because the walls have new wallpaper on them, the pipe must not scratch the wall. That is, the pipe must always occupy only empty cells.

There are 3 directions in which the pipe can be pushed: →, ↘, and ↓. The pipe can be rotated while being pushed. It can only be rotated by 45 degrees, and the pushing direction must be right, down, or the diagonal direction down-right.

When the pipe lies horizontally there are 2 possible moves, when it lies vertically there are 2, and when it lies diagonally there are 3.

The figures below show all possible moves depending on the pipe's orientation, and the places that must be empty are marked with color.

Horizontal

Vertical

Diagonal

Initially, the pipe occupies (1, 1) and (1, 2), and its orientation is horizontal. Find the number of ways to move one end of the pipe to (N, N).

Input

The first line gives the size of the house N (3 ≤ N ≤ 32). From the second line, N lines give the state of the house. An empty cell is given as 0, and a wall as 1. (1, 1) and (1, 2) are always empty.

Output

Print the number of ways to move one end of the pipe to (N, N) on the first line. If it cannot be moved, print 0.

Examples5

  1. Example 1

    Input
    3
0 0 0
0 0 0
0 0 0
    Expected output
    1

  2. Example 2

    Input
    4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
    Expected output
    3

  3. Example 3

    Input
    5
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
    Expected output
    0

  4. Example 4

    Input
    6
0 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
    Expected output
    13

  5. Example 5

    Input
    22
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    Expected output
    4345413252