TwoCatsAndAMouse
SRM 826 · 2022-03-28 · by misof
Problem Statement
Two distinct cats are chasing a mouse.
The whole action is happening on squares of an R times C grid, with R >= C. Each of the three actors is always located in one of those squares. The cats may share the same square.
Squares have coordinates from (0, 0) to (R-1, C-1). Squares also have IDs from 0 to R*C-1 in row major order: the ID of square (r, c) is r*C + c.
The cats and the mouse take alternating turns: in odd-numbered turns (1, 3, 5, ...) both cats may move independently of each other, in even-numbered turns (2, 4, ...) the mouse may move.
Each movement consists of either staying in the current square or moving to another square of the grid that shares a side with the old square. Movements from (r, c) to (r, c), (r-1, c), (r+1, c), (r, c-1) and (r, c+1) will be assigned values 0, 1, 2, 3 and 4, respectively.
The mouse may never move into a location that has a cat. If either or both cats move into the location that contains the mouse, the chase is over and the cats win.
You are given the dimensions of the grid. Determine whether the cats can win for all possible starting positions of the two cats and the mouse if the game is played on the given grid.
If the mouse is sometimes able to survive indefinitely, return an empty
Otherwise, let N = 4*R + 2*C. There is always a strategy with which the cats will catch the mouse in at most N turns. (I.e., at most N/2 turns in which cats move and the corresponding N/2 turns in which the mouse moves.) Find and return the description of any one such strategy.
Output format if a solution exists: consider all triples (c1, c2, m) where 0 <= c1, c2, m < R*C and m is different from c1 and c2. For each of these triples, in lexicographic order, consider the situation where cat 1 is on the square with ID c1, cat 2 on c2, and mouse on m. Determine how you want the two cats to move, take the corresponding move values v1 (for cat 1) and v2 (for cat 2) and write down the character with ASCII value 65 + 5*v1 + v2. Return the concatenation of all these characters.
Notes
- The statement about the strategy in at most N turns existing is true for arbitrary large R and C. The small actual constraints are used to make sure that it is possible to return the complete strategy.
Constraints
- R and C will be positive.
- R will be greater than or equal to C.
- R*C will be between 2 and 20, inclusive.
2 2 Returns: "UKOKCUEUKCKPNKPKPDEUFUFJUFBFPDPBFIFP"
All possible configurations of the two cats and the mouse are shown below in lexicographic order, with '1' and '2' representing the two cats and 'M' representing the mouse. The value '3' is used for situations where both cats share the same square. 3M 3. 3. 12 12 1M 1. 1M 1. .. M. .M M. .M 2. 2M .2 M2 21 21 M3 .3 .3 M1 .1 M1 .1 M. .M .. M. .M 2. 2M .2 M2 2M 2. M2 .2 M. .M .. M. .M 1. 1M 1. 1M 3. 3. 3M 12 12 2M 2. M2 .2 M. .M M. .M .. .1 M1 .1 M1 21 21 .3 .3 M3 In 34 of these 36 configurations at least one of the cats is adjacent to the mouse. In all such situations our return value describes a move in which one of the cats catches the mouse while the other remains stationary. For example, character 3 of the return value has ASCII value 65 + 2*5 + 0, meaning that cat 1 is moving in direction 2 (down one row) while cat 2 is moving in direction 0 (staying put). In the two remaining situations our two cats move to the two different squares adjacent to the mouse's square. (The mouse then must remain stationary in its turn and it is then caught the next turn.) For example, character 2 of the return value has ASCII value 65 + 2*5 + 4, meaning that cat 1 is moving in direction 2 (down one row) while cat 2 is moving in direction 4 (right one column).
6 1 Returns: "KMMMMCMMMKCMMKBCMKLBCKLLBKMMMFKMMMFCMMFKCMFKBCFKLBFKMMBKMMGFKMMGFCMGFKCGFKBCFKMBFKMGBKMGGFKMGGFCGGFKCHFKBCFKGBFKGGBKGGGFKGGGFCHHFBCHFGBCFGGBFGGGBGGGGF"
Here the return value describes the strategy in which each cat goes towards the mouse. (Except for the cases when both would catch it at the same time. In those cases one of the cats remains in its place.)
2 1 Returns: "KF"
3 1 Returns: "KMCKKFKFFBGF"
4 1 Returns: "KMMCMKCKBKMFKMFCFKFKBKGFKGFCFBFGBGGF"
Submissions are judged against all 18 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TwoCatsAndAMouse with a public method string catchMouse(int R, int C) · 18 test cases · 2 s / 256 MB per case