Moving a Pipe 1

Interview

Time limit1sMemory limit512 MB

Summary
Count the ways to push a two-cell pipe (horizontal, vertical, or diagonal) across an N by N grid of walls until one end reaches (N, N).
Level

Medium6 of 10

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

Problem

Yuhyeon has moved into a new house. The house is 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, both starting from 1. Each cell is either empty or a wall.

Today, to repair the house, Yuhyeon wants to move one pipe. The pipe has the shape shown below and occupies two consecutive cells.

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

Because the pipe is very heavy, Yuhyeon pushes the pipe to move it. New wallpaper was put on the walls, so the pipe must not scratch them. In other words, the pipe must always occupy empty cells only.

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

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 for each pipe orientation, and cells that must be empty are marked with color.

Horizontal

Vertical

Diagonal

Initially the pipe occupies (1, 1) and (1, 2) and 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 ≤ 16). The next N lines give the state of the house. An empty cell is 0 and a wall is 1. (1, 1) and (1, 2) are always empty.

Output

On the first line, print the number of ways to move one end of the pipe to (N, N). If it cannot be moved, print 0. The number of ways is always less than or equal to 1,000,000.

Examples4

  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