You thought you had vanquished every maze’s challenge: first outwitting the AI debug-bot in Polymorphic Pacman: Parallel Pursuit, then mastering the power-dot frightened mode in Polymorphic Pacman II. Yet the simulators will not let you go so easily. The monitors in the NTHU CS lab flicker once more, and you find yourself hurled into a new, even more twisted world.
In this "final stage" of your nightmarish odyssey:
#) remain impenetrable barriers (packed bookshelves, locked lab doors).It still contains ordinary dots O, but now ten power‑dots X are spread across the map.
Whenever Pacman eats a power‑dot:
Succeeding in these tasks will finally tear you out of the simulation and return you to your world—just in time to welcome summer vacation.
You must modify the provided code at each part marked "TODO" to help Pacman evade the ghost and clear all the dots.
Every round, your Pacman can:
Move to any of the four adjacent cells (up, down, left, right) that aren't walls.
Choose to stay still and not move this round.
Note that the maze wraps around both horizontally and vertically: moving off the right edge into column M is treated as moving into column 0, and moving off the left edge into column −1 is treated as moving into column M − 1, provided the destination cell is not a wall. The same applies vertically for rows.
(Already implemented; modifying it is not recommended)
Ghost has 10% chance to move randomly to an adjacent non-wall cell.
Ghost has 90% performs a breadth‐first search (BFS) from its current position to Pacman’s current position, and then moves exactly one step along the resulting shortest path—moving toward Pacman if in normal mode, or away from Pacman if in frightened mode.
Ghost never remain stationary.
Ghost will never move onto a power-dot cell (X).
Avoid changing parts of the code not marked by "TODO" unless you're absolutely sure what you're doing.
Modifying ghost movement logic to avoid capture is strongly discouraged. The judge system will recreate ghost paths based on your provided random seed. If your output differs from the judge's expected ghost path, you will receive a "Wrong Answer."
When pacman moves and may eat O/X :
While the frightened timer > 0:
Ghost moves away from Pacman.
If Pacman lands on the blue ghost, ghost disappears and re-spawns after 10 rounds.
At end of each round:
if timer = 0, the surviving blue ghost reverts to normal.
timer--;
There are exactly 10 power-dots in each test case.
To pass each testcase, you should:
1 ≤ N, M ≤ 40
5 × N × M ≤ T ≤ 10 × N × M
It is guaranteed that no cell in the map is enclosed by walls on three sides (meaning every cell has at least two accessible paths).
It is guaranteed that Pacman can always clear all dots.
Uncomment the following two lines inside int main() in the provided code:
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
Place your input data into a file named input.txt (make sure it’s in the same directory as your program).
After execution, your program's output will be stored in output.txt.
#include <bits/stdc++.h>
using namespace std;
int T, N, M;
vector<string> grid;
struct Position {
int x, y;
bool operator==(const Position& other) const {
return x == other.x && y == other.y;
}
bool operator<(const Position& other) const {
return (x != other.x) ? (x < other.x) : (y < other.y);
}
int operator-(const Position& other) const {
/// TODO-01:
// Implement the BFS algorithm to find the distance between two positions.
}
void fixedPos() {
x = (x + N) % N;
y = (y + M) % M;
}
};
set<Position> dots;
set<Position> power_dots;
class Entity {
public:
Entity(Position pos): pos(pos) {}
virtual ~Entity() = default;
virtual void move() = 0;
Position getPosition() const {
return pos;
}
void fixedPos() {
pos.fixedPos();
}
protected:
Position pos;
};
class Pacman : public Entity {
public:
Pacman(Position pos): Entity(pos) {}
void setGhostPos(const Position& pos) {
ghostPosition = pos;
}
void move() override {
// TODO-02:
// Implement how Pacman moves in each round.
}
private:
// TODO (optional):
// You may want to add some extra variables here.
Position ghostPosition;
int scaredTimer = 0;
};
class Ghost : public Entity {
public:
Ghost(Position p): Entity(p), startPosition(p) {}
void setPacmanPos(const Position& pos) {
pacmanPosition = pos;
}
void setFrightened(bool f) {
frightened = f;
}
void stateUpdate() {
if (!alive) {
if (timer == 0) {
revive();
}
timer--;
return;
}
}
bool isAlive() const {
return alive;
}
bool isFrightened() const {
return frightened && alive;
}
void eaten() {
alive = false;
frightened = false;
pos = startPosition;
timer = 10;
}
void revive() {
alive = true;
frightened = false;
pos = startPosition;
}
void move() override {
if (!alive) return;
vector<Position> nbrs;
static const int dxs[4] = {-1, 1, 0, 0};
static const int dys[4] = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
Position nbr = pos;
nbr.x += dxs[i];
nbr.y += dys[i];
nbr.fixedPos();
if (grid[nbr.x][nbr.y] != '#' && grid[nbr.x][nbr.y] != 'X') {
nbrs.push_back(nbr);
}
}
for(auto i:power_dots) {
grid[i.x][i.y] = '#';
}
int now_dis;
Position chosen = pos;
double p = (double)rand() / RAND_MAX;
if (p < 0.9) {
if(frightened) {
now_dis = 0;
if (!nbrs.empty()) {
for (Position& c : nbrs) {
int d = c - pacmanPosition;
if (d >= now_dis) {
chosen = c;
now_dis = d;
}
}
}
}
else{
now_dis = INT_MAX;
if (!nbrs.empty()) {
for (Position& c : nbrs) {
int d = c - pacmanPosition;
if (d <= now_dis) {
chosen = c;
now_dis = d;
}
}
}
}
}
else {
int idx = rand() % nbrs.size();
chosen = nbrs[idx];
}
for(auto i:power_dots) {
grid[i.x][i.y] = 'X';
}
pos = chosen;
}
private:
Position startPosition, pacmanPosition;
bool alive = 1, frightened = 0;
int timer = 0;
};
ostream& operator<<(ostream& os, const Position& p) {
os << p.x << ' ' << p.y;
return os;
}
ostream& operator<<(ostream& os, const Entity& e) {
os << e.getPosition();
return os;
}
class GameMap {
public:
GameMap(const vector<string>& g) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (grid[i][j] == 'O'){
dots.insert({i, j});
}
else if (grid[i][j] == 'X') {
power_dots.insert({i, j});
}
}
}
}
void handlePacmanCell(const Position& pacman, Ghost& ghost) {
if (grid[pacman.x][pacman.y] == 'O'){
grid[pacman.x][pacman.y] = '.';
dots.erase(pacman);
}
else if (grid[pacman.x][pacman.y] == 'X'){
grid[pacman.x][pacman.y] = '.';
if(ghost.isAlive()){
frightenedTimer = 10;
ghost.setFrightened(true);
}
power_dots.erase(pacman);
}
}
void updateTimer(Ghost& ghost) {
if (frightenedTimer > 0) frightenedTimer--;
if (frightenedTimer == 0) {
ghost.setFrightened(false);
}
}
void resolveCollision(Pacman& pacman, Ghost& ghost) {
if (!ghost.isAlive()) return;
if (pacman.getPosition() == ghost.getPosition()) {
if (ghost.isFrightened()) {
ghost.eaten();
}
}
}
private:
int frightenedTimer;
};
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
cin >> T >> N >> M;
grid.resize(N);
for (int i=0;i<N;i++) cin >> grid[i];
Position pacman_start, ghost_start;
for (int i=0;i<N;i++) for (int j=0;j<M;j++) {
if (grid[i][j]=='P') pacman_start = {i,j};
if (grid[i][j]=='G') ghost_start = {i,j};
}
unsigned GHOST_SEED = /* TODO-03: */ ;
// Choose any integer you like as a random seed! It will affect how the ghosts move.
// Note: make sure the number you pick fits within the range of an unsigned integer (0 to 4,294,967,295),or unexpected results may happen.
srand((unsigned)GHOST_SEED);
GameMap gameMap(grid);
Pacman pacman(pacman_start);
Ghost ghost(ghost_start);
for (int t=0; t<T; t++) {
pacman.setGhostPos(ghost.getPosition());
pacman.move();
pacman.fixedPos();
gameMap.handlePacmanCell(pacman.getPosition(), ghost);
gameMap.resolveCollision(pacman, ghost);
ghost.setPacmanPos(pacman.getPosition());
ghost.move();
ghost.fixedPos();
gameMap.resolveCollision(pacman, ghost);
ghost.stateUpdate();
gameMap.updateTimer(ghost);
cout << pacman << ' ';
if(ghost.isAlive()) cout << ghost << '\n';
else cout << "-1 -1" << '\n';
}
cout << GHOST_SEED <<'\n';
return 0;
}
(Input handling is already implemented in the provided code.)
The first line contains three integers T, N and M, representing the number of rounds T and the dimensions of the maze ( N × M ) .
The next N lines each contain M characters ci,j, where:
ci,j = '#' represents a wall.
ci,j = '.' represents an empty space.
ci,j = 'O' represents a dot.
ci,j = 'X' represents a power dot.
ci,j = 'P' represents Pacman's initial position.
ci,j = 'G' represents a ghost's initial position.
(Output handling is already implemented in the provided code.)
Output ( T + 1 ) lines:
For the first T lines, each line should contain four integers Px, Py, Gx, Gy, representing Pacman's position (Px, Py) and the ghost's position (Gx, Gy) at each round from 1 to T.
The ( T + 1 ) th line should output your chosen random seed.
If multiple valid solutions exist, outputting any one of them will be accepted.