Grid Paths

You are given a 2D grid A of size N x N. Rows are numbered from top to bottom from 0 to N - 1 and the columns are numbered from left to right from 0 to N - 1.

From a cell, you can either move left, right, up, and down. You cannot move outside of the grid. Some cells are blocked. A cell is blocked if A[i][j] is 0, otherwise A[i][j] denotes the value at i^th row and j^th column.

Consider every path from (0, 0) to (N-1, N-1) which visits each unblocked cell exactly once. The cost of a path is the sum of absolute values of adjacent cells of the path. Formally, if the values of the path are B₁, B_{2, ...,}, B_r, the cost of the path is ∑ | B_i - B_i-1 | for i from 2 to r.

Find the sum of the cost of all such paths.

Note : Interpreter languages like Python may not work. Please try it in languages like C/ C++/ Java.

2 <= N <= 7

0 <= A[i][j] <= 100

0 < A[0][0], A[N-1][N-1] <= 100

Input 1:

  A : 
  [
    [5, 2]
    [0, 7]
  ]

Input 2:

  A : 
  [
    [79, 19, 59]
    [45, 89, 63]
    [79, 81, 37]
  ]

Output 1:

  8

Output 2:

  472

Explanation 1:

  Valid path is [5, 2, 7]. Cost is |5-2| + |7-2| = 8 

Explanation 2:

  There are two valid paths-
  1. [79, 19, 59, 63, 89, 45, 79, 81, 37]
  Cost = 254
  2. [79, 45, 79, 81, 89, 19, 59, 63, 37]
  Cost = 218