There is an n × n grid of squares. Each square is either special, or has a positive integer cost assigned to it. No squa

[answerhappygod]

There is an n × n grid of squares. Each square is eitherspecial, or has a positive integer costassigned to it. No square on the border of the grid isspecial.A set of squares S is said to be good if it does not contain anyspecial squares and, starting fromany special square, you cannot reach a square on the border of thegrid by performing up, down,left and right moves without entering a cell belonging to S.
- Design an algorithm which receives an arbitrary n × n grid,runs in time poly-nomial in n and determines a good set of squares with minimum totalcost.