Answer Happy

The following question involves maximum flowalgorithms, namely Ford- Fulkerson andEdmonds-Karp.
Just do question 1.1 below. The yellow and green partsare hints. Explain the answer only using words, numbers and/orpseudocode.
There is an n x n grid of squares. Each square is either special, or has a positive integer cost assigned to it. No square on the border of the grid is special. A set of squares S is said to be good if it does not contain any special squares and, starting from any special square, you cannot reach a square on the border of the grid by performing up, down, left and right moves without entering a cell belonging to S. 1.1 [5 marks] In the following diagram, squares are labelled 'X' if they are special, otherwise they are labelled by their cost. Identify a good set of squares with minimum total cost for this particular grid. 5349 4 X 3 6 1 9 X 4 1 2 3 5 Consider paths from the 'X' squares to the border of the grid. A set of squares is good if each of these paths contains at least one of the chosen squares. 1.2 [15 marks] Design an algorithm which receives an arbitrary n x n grid, runs in time poly- nomial in n and determines a good set of squares with minimum total cost. Refer to question 1.2 of problem set 4 for an example of a flow network corresponding to a grid. • Can border squares be included in S? Yes. If a border square is included in S then it successfully impedes any path from a special square to itself. • Do the values contained in its squares have to be distinct? No. S can include two or more squares containing equal values.