sumInPerimeter

You are given a grid of integers and an integer p. Each cell of the grid is a 1 x 1 square. Your task is to find a 4-connected set of elements in the gridthat has a perimeter equal to p and has the highest possible sum. Return this sum.

Example

• For

  grid = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]

and p = 6 the output should be sumInPerimeter(grid, p) = 17.

A perimeter of 6 will surround two elements in a grid. The two elements with a perimeter of 6 in this grid that have the maximum possible value are 8and 9, with a sum of 17.

Input/Output:

• [execution time limit] 0.5 seconds 

• [input] array.array.integer grid
  1 ≤ grid.length ≤ 20,
  1 ≤ grid[i].length ≤ 20,
  -105 ≤ grid[i][j] ≤ 105.

• [input] integer p

  An even integer.4 ≤ p ≤ 24.

• [output] integer

  The maximum possible sum of cells inside of a perimeter with a length of p.