Page 1 of 1
Problem 4. [25 pts] [PlacingTokens] We have a grid M of size nxn where each cell is either White or Black. Describe a po
Posted: Thu May 05, 2022 12:56 pm
by answerhappygod
- Problem 4 25 Pts Placingtokens We Have A Grid M Of Size Nxn Where Each Cell Is Either White Or Black Describe A Po 1 (53.81 KiB) Viewed 47 times
Problem 4. [25 pts] [PlacingTokens] We have a grid M of size nxn where each cell is either White or Black. Describe a polynomial- time algorithm to place token on the grid using network flows such that the following two conditions are met: 1. Every token is placed on a white cell 2. Each row and each column of the grid has exactly one token See the example of a valid placement of tokens on the Figure 1. The algorithm should detect if no such placement exists. Figure 1: Example of a valid placement of tokens on a grid