Cutting the Stone Slab

Time limit2sMemory limit128 MB

Summary
Count the number of ways to repeatedly cut an N x N stone slab with alternating horizontal/vertical straight cuts so every final piece has no impurity and exactly one crystal.
Level

Hard8 of 10

Topics
Dynamic programming, Recursion, Combinatorics, Matrix
Solved
No attempts yet

Problem

A stone slab is given as an N x N grid. Each cell is empty, contains an impurity, or contains a crystal. You want to cut the slab into pieces so that every final piece satisfies both conditions below.

  • The piece contains no impurity.
  • The piece contains exactly one crystal.

To remove an impurity, a cut must be a straight line passing through a cell that contains an impurity. Because of the grain of the slab, each cut must be horizontal or vertical. The first cut may use either direction, but when a resulting piece is cut again, the new cut cannot have the same direction as the cut that created that piece.

A cut line must pass all the way across the current piece and split it into two pieces. A line containing a crystal cannot be cut. Count all possible cutting processes.

Input

The first line contains the size N of the slab. 1 <= N <= 20.

Each of the next N lines contains N integers describing one row of the slab, separated by spaces.

  • 0: empty cell
  • 1: impurity
  • 2: crystal

The number of crystals is at most 15.

Output

Print the number of ways to cut the slab so that every final piece contains no impurity and exactly one crystal.

If there is no possible way, print -1.

Examples2

  1. Example 1

    Input
    8
0 0 0 0 0 2 0 0
0 0 0 0 0 0 1 0
0 0 2 1 0 0 2 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 2 1 0 0 0
0 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0
    Expected output
    1

  2. Example 2

    Input
    5
0 0 0 0 0
0 2 2 0 0
0 1 1 1 0
0 2 1 2 0
2 0 0 0 0
    Expected output
    -1