Problem Statement |
| | There is an n by n grid of network nodes. Each node is either standard, or a token consumer. Element i of setup, which corresponds to row i of the grid, will contain a single space delimited list of n values. A consumer will be denoted by an 'X' character. A standard node is denoted by a nonnegative integer with no extra leading zeros, which represents how many tokens it possesses. An unknown will be denoted by a '_' character (there will be exactly 1 unknown).
Suppose a particular standard node is adjacent to d nodes (upward, downward, leftward, or rightward with no wrap-around), and has at least d tokens. Then that node can send 1 token to each adjacent node leaving it with d fewer tokens. For example, a node in the corner with at least 2 tokens could send. Token consumers accept tokens but never send them. finish, which is formatted like setup but with the '_' character replaced by a number, should describe the state of the network after all possible tokens have been sent, and no more can be sent. Return the smallest possible nonnegative value of the unknown, or -1 if no value will work. If finish does not describe a network where tokens cannot be sent (a standard node has too many tokens), also return -1. |
| |
Definition |
| | | Class: | TokenGrid | | Method: | getUnknown | | Parameters: | String[], String[] | | Returns: | int | | Method signature: | int getUnknown(String[] setup, String[] finish) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The order in which nodes send their tokens is irrelevant. |
| |
Constraints |
| - | setup and finish will be formatted as described in the problem statement. |
| - | setup will contain between 2 and 4 elements inclusive. |
| - | setup and finish will agree on the placement of consumer nodes. |
| - | setup and finish will contain the same number of elements. |
| - | Each integer in setup and finish will be between 0 and 50 inclusive. |
| - | setup will contain at least 1 consumer node. |
| |
Examples |
| 0) | |
| | {"X X",
"X _"} | {"X X",
"X 0"} |
| Returns: 0 | |
|
| 1) | |
| | {"X X",
"X _"} | {"X X",
"X 2"} |
| Returns: -1 | | The lower right node in finish can send its tokens, so we immediately return -1.
|
|
|
| 2) | |
| | {"X 2",
"X _"} | {"X 1",
"X 0"} |
| Returns: 1 | If the unknown node begins with 1 token, the following sequence of scenarios occurs:
X 2 ---> X 0 ---> X 1
X 1 X 2 X 0
|
|
|
| 3) | |
| | {"0 0 0 0",
"0 0 0 0",
"0 0 0 0",
"_ 0 0 X"} | {"1 1 0 1",
"2 2 2 1",
"2 3 3 2",
"0 1 1 X"} |
| Returns: 26 | |
|
| 4) | |
| | {"50 50 50 X",
"X 50 50 50",
"50 50 50 50",
"X 50 50 _"
} | {"1 1 2 X",
"X 1 3 2",
"2 2 2 2",
"X 2 2 1"
} |
| Returns: 563 | |
|