Problem Statement | |||||||||||||
You are the most popular programmer in town and the mayor needs your help. This time he wishes to reorganize the town's detention system. All the inmates are held in an underground rectangular-shaped prison, with cells situated on m rows and n columns. When opened, the cells communicate with each other vertically and horizontally. Thus, the distance between two cells is defined as the Manhattan distance: The mayor's plan is to reduce the conflicts by placing the prisoners as far from each other as possible. There are nr prisoners to place and each cell can hold at most one prisoner. The goal is to put the prisoners in cells such that the minimum of all the distances between two occupied cells is as high as possible. Given an int m, an int n and an int nr representing the number of rows, the number of columns and the number of prisoners, respectively, return an int denoting the highest possible minimum distance between two occupied cells. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Constraints | |||||||||||||
- | m is between 1 and 4, inclusive. | ||||||||||||
- | n is between 1 and 4, inclusive. | ||||||||||||
- | nr is between 2 and n*m, inclusive. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
| |||||||||||||
3) | |||||||||||||
|