A cat and a mouse are trapped in a 20x20 maze. Each cell is one of the following types:
'S': starting position'E': exit position'#': wall'.': empty cellTwo cells are adjacent if they share a side, that is, if one is directly above, below, to the left of, or to the right of the other.
The cat and the mouse are not allowed to be in the same cell at any time.
The cat starts at 'S' and the mouse starts at 'E'.
Initially, the entire maze is unknown to both the cat and the mouse.
The game proceeds in turns. In each turn, the cat and the mouse act in the following order:
They know the current turn number (step), the position of the other, and the position of the exit.
Your goal is to make the cat reach the exit cell within 4000 turns. This is guaranteed to be possible for all given test cases.
HINT
The following strategy works.
Steps 0–799: The cat explores all reachable cells without entering the mouse’s cell. (The mouse stays still.)
Steps 800–1599: The cat moves to a discovered reachable that is farthest from 'E'.
Steps 1600–2399: The mouse explores all reachable cells without entering the cat’s cell.
Steps 2400–3199: The mouse moves to a discovered reachable cell that does not block the cat from reaching 'E'.
'E'.Steps 3200–3999: The cat moves to 'E'.
Code
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
const int SIZE = 20;
const int MAX_STEPS = 4000;
const int INF = 1000000000;
enum class Direction {
Up,
Down,
Left,
Right,
Stay
};
struct Pos {
int r, c;
Pos operator+(Direction dir) const {
switch (dir) {
case Direction::Up:
return {r - 1, c};
case Direction::Down:
return {r + 1, c};
case Direction::Left:
return {r, c - 1};
case Direction::Right:
return {r, c + 1};
}
return {r, c}; // Direction::Stay
}
bool operator==(const Pos& other) const {
return r == other.r and c == other.c;
}
bool operator!=(const Pos& other) const {
return r != other.r or c != other.c;
}
};
class MemoryMap {
private:
char memory[SIZE][SIZE];
int visited[SIZE][SIZE];
public:
MemoryMap(Pos startPos, char startCell) {
fill(memory[0], memory[0] + SIZE * SIZE, '?');
memory[startPos.r][startPos.c] = startCell;
resetVisited(startPos);
}
char getCell(Pos p) const {
return memory[p.r][p.c];
}
void setCell(Pos p, char cell) {
memory[p.r][p.c] = cell;
}
bool knownOpen(Pos p) const {
return memory[p.r][p.c] != '#' and memory[p.r][p.c] != '?';
}
void resetVisited(Pos pos) {
fill(visited[0], visited[0] + SIZE * SIZE, 0);
visited[pos.r][pos.c] = 2;
}
// Performs one step of a DFS walk and returns the chosen direction.
// Remember to call resetVisited(pos) before starting a new DFS search.
Direction dfsNextDirection(Pos& pos, Pos target, Pos untouchable) {
/*
This method performs one step of a DFS walk from pos through known open cells.
It avoids untouchable when visiting new cells, and stops when it reaches target.
The parameter pos is the current position of the player. This method updates
pos to the next position chosen by DFS, and returns the direction of that move.
The parameter untouchable is usually the position of the other player
(cat / mouse).
To use this method:
1. Call resetVisited(pos) before starting a new DFS search.
2. Repeatedly call dfsNextDirection(pos, target, untouchable).
3. If target or untouchable changes, call resetVisited(pos) before continuing.
4. If target is reached, this method returns Direction::Stay.
5. To explore all reachable known cells, use an impossible target such as {-1, -1}.
*/
Direction dirs[4] = {
Direction::Up,
Direction::Down,
Direction::Left,
Direction::Right
};
if (pos == target) {
return Direction::Stay;
}
for (int i = 0; i < 4; i++) {
Pos p = pos + dirs[i];
if (knownOpen(p) and visited[p.r][p.c] == 0 and p != untouchable) {
visited[p.r][p.c] = visited[pos.r][pos.c] + 1;
pos = p;
return dirs[i];
}
}
for (int i = 0; i < 4; i++) {
Pos p = pos + dirs[i];
if (visited[p.r][p.c] == visited[pos.r][pos.c] - 1) {
visited[pos.r][pos.c] = -1;
pos = p;
return dirs[i];
}
}
return Direction::Stay;
}
// TODO: Use BFS to compute shortest distances from start to all known open cells.
void computeDistance(Pos start, int distance[SIZE][SIZE]) const;
};
class Cat {
private:
MemoryMap memory_map;
Pos pos;
Pos target;
// HINT(optional): You may use these variables if you need them.
int phase;
int direction;
int state[SIZE];
public:
// TODO: Initialize the cat.
Cat(Pos startPos);
// TODO: Update the cat's memory using the visible neighboring cells.
void see(char up, char down, char left, char right);
// TODO: Move the cat and return the chosen direction.
Direction move(int step, Pos mousePos, Pos exitPos);
};
class Mouse {
private:
MemoryMap memory_map;
Pos pos;
Pos target;
// HINT(optional): You may use these variables if you need them.
int phase;
int direction;
int state[SIZE];
public:
// TODO: Initialize the mouse.
Mouse(Pos startPos);
// TODO: Update the mouse's memory using the visible neighboring cells.
void see(char up, char down, char left, char right);
// TODO: Move the mouse and return the chosen direction.
Direction move(int step, Pos catPos, Pos exitPos);
};
class Game {
private:
const vector<string> maze;
Pos catPos;
Cat cat;
Pos exitPos;
Pos mousePos;
Mouse mouse;
string catSteps;
string mouseSteps;
char getCell(Pos p) const {
return maze[p.r][p.c];
}
Pos findCell(char cell) const {
for (int i = 0; i < SIZE; i++) {
if (auto it = maze[i].find(cell); it != string::npos) {
return {i, int(it)};
}
}
return {-1, -1};
}
bool success() const {
return catPos == exitPos;
}
char directionToChar(Direction dir) const {
switch (dir) {
case Direction::Up:
return 'U';
case Direction::Down:
return 'D';
case Direction::Left:
return 'L';
case Direction::Right:
return 'R';
case Direction::Stay:
return 'S';
}
return 'S';
}
bool illegal(Pos p) const {
return p.r < 0 or p.r >= SIZE or p.c < 0 or p.c >= SIZE or getCell(p) == '#';
}
public:
Game(const vector<string>& inputMaze)
: maze(inputMaze),
catPos(findCell('S')),
cat(catPos),
exitPos(findCell('E')),
mousePos(exitPos),
mouse(mousePos)
{}
void play() {
for (int step = 0; step < MAX_STEPS; step++) {
cat.see(
getCell(catPos + Direction::Up),
getCell(catPos + Direction::Down),
getCell(catPos + Direction::Left),
getCell(catPos + Direction::Right)
);
Direction catDir = cat.move(step, mousePos, exitPos);
catSteps += directionToChar(catDir);
catPos = catPos + catDir;
if (catPos == mousePos or illegal(catPos) or success()) {
break;
}
mouse.see(
getCell(mousePos + Direction::Up),
getCell(mousePos + Direction::Down),
getCell(mousePos + Direction::Left),
getCell(mousePos + Direction::Right)
);
Direction mouseDir = mouse.move(step, catPos, exitPos);
mouseSteps += directionToChar(mouseDir);
mousePos = mousePos + mouseDir;
if (mousePos == catPos or illegal(mousePos)) {
break;
}
}
cout << catSteps << '\n' << mouseSteps << '\n';
}
};
int main() {
vector<string> inputMaze(SIZE);
for (string& row : inputMaze) {
cin >> row;
}
Game game(inputMaze);
game.play();
return 0;
}
(The input is already handled by the provided C++ code.)
The input contains exactly 20 lines.
Each line contains exactly 20 characters, representing the maze.
The maze contains exactly one 'S' and exactly one 'E'.
The outer boundary of the maze is guaranteed to be '#'. (See the sample input for an example.)
Subtasks
(The output is already handled by the provided C++ code.)
The provided main function prints two lines:
Each move is represented by one character:
'U': move up'D': move down'L': move left'R': move right'S': stay in the same cellThe special judge accepts the output if, after simulating the two strings, all moves are legal, the cat and mouse are never in the same cell, and the cat reaches 'E' within 4000 steps. Otherwise, the special judge rejects the output.