MAZE problem with added factors.

You are given a matrix NxM.

2 denotes starting position, 1 denotes wall, 0 denotes free space , x denotes points in that cell.

You starts from the cell having 2 . You can go up, right, down or left. While travelling through matrix you can break at max only 3 walls and you cannot go through the cell contains further wall . Find the maximum points you can collect.

1 <= N, M <= 10

7 6

2 0 0 0 1 0

1 1 1 1 1 0

1 1 1 0 0 0

0 20 1 20 0 0

1 1 1 1 1 0

1 30 1 1 20 0

Solution of above e.g. is 20+20+30 = 70

Normal backtracking isn’t working on it . Can anyone help ?