Problem Statement |
| | You have recently bought a field containing gold and silver, and you want to hire some workers to gather the treasure and build beautiful things with it. The field is divided into square cells of equal size. You are given a String[] field, where the j-th character of the i-th element is the content of the cell at row i, column j. A period ('.') represents grass, an uppercase 'X' represents rocks, and uppercase 'G' and 'S' represent gold and silver, respectively. You have also built special workplace cells for your workers, each denoted by an uppercase 'W'.
Each worker must be assigned exactly one workplace, one gold cell and one silver cell. None of these three cells can be assigned to any of the other workers. Each worker will be transporting gold and silver from his cells to his workspace, and for efficiency reasons, you do not want workers to carry anything for more than K meters. This means every worker's workplace must be at most K meters away from his gold cell and at most K meters away from his silver cell. Distance is measured as follows. From each cell, a worker can only move left, right, up or down to an adjacent cell (if one exists). The distance between two consecutive cells is one meter. Workers are only allowed to walk on grass when moving between their cells.
Return the largest number of workers you can hire while meeting these requirements. |
| |
Definition |
| | | Class: | WorkersOnPlane | | Method: | howMany | | Parameters: | String[], int | | Returns: | int | | Method signature: | int howMany(String[] field, int K) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | field will contain between 1 and 30 elements, inclusive. |
| - | Each element of field will contain between 1 and 30 characters, inclusive. |
| - | Each element of field will contain the same number of characters. |
| - | Each character in each element of field will be a period ('.'), an uppercase 'X', an uppercase 'G', an uppercase 'S' or an uppercase 'W'. |
| - | K will be between 1 and 1000, inclusive. |
| |
Examples |
| 0) | |
| | { "G..X",
"..XS",
"W..." } | 5 |
| Returns: 1 | |
|
| 1) | |
| | { "GG..",
"....",
"..W.",
"..W.",
"SS.." } | 4 |
| Returns: 2 | |
|
| 2) | |
| | { "GG..",
"XX..",
"..W.",
"..W.",
"SS.." } | 10 |
| Returns: 1 | | We can hire only one worker, because the gold mine in the top left corner can't be reached from any of the workplaces. |
|
|
| 3) | |
| | | Returns: 0 | | If we hire a worker for the left workplace, he won't be able to reach any of the silver mines. Similarly, if we hire a worker for the right workplace, he won't be able to reach gold mines. So we can't hire anybody. |
|
|