You had barely escaped the original Pacman world, your heart still pounding, when suddenly the monitors in the National Tsing Hua University CS lab flickered once again, pulling you into a new maze!
As a Computer Science student at NTHU, you had stayed up late testing your friends' AI-driven Pacman simulator. One moment you were celebrating your narrow escape, the next—the desks and lights of the lab melted away, replaced by a strange maze filled with dots and a lone ghost. You looked down and realized: you had become Pacman!
In this parallel campus:
The maze is an N × M grid, representing the layout of the CS building. It wraps around both horizontally and vertically on the left and right edges, as well as the top and bottom edges, are considered adjacent if neither is a wall—forming a toroidal structure.
Walls (#) are packed bookshelves or locked lab doors; open spaces (.) are clear hallways; dots (O) float where projectors once shone.
Your starting position (P) is the console where you appeared. A single ghost (G)—an AI debug-bot—chases you relentlessly, always using BFS to determine the shortest path and moving exactly one step each round.
Your mission remains clear: Eat every dot without being caught by the ghost. Once you successfully collect all dots, the simulation will finally end, returning you safely to your own world—and tomorrow's lecture on Introduction to Programming (II).
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 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.
Ghost never remain stationary.
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."
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) ? (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;
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;
};
class Ghost : public Entity {
public:
Ghost(Position pos): Entity(pos){}
void setPacmanPos(const Position& pos) {
pacmanPosition = pos;
}
void move() override {
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] != '#') {
nbrs.push_back(nbr);
}
}
int now_dis = INT_MAX;
Position chosen = pos;
double p = (double)rand() / RAND_MAX;
if (p < 0.9) {
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];
}
pos = chosen;
}
private:
Position pacmanPosition;
};
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});
}
}
}
}
void eatDot(const Position& p) {
if (dots.find(p) != dots.end()) {
dots.erase(p);
}
}
};
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.eatDot(pacman.getPosition());
ghost.setPacmanPos(pacman.getPosition());
ghost.move();
ghost.fixedPos();
cout << pacman << ' ' << ghost << '\n';
}
cout << GHOST_SEED <<'\n';
return 0;
}
A visualization tool is provided to help you debug your solution.
Paste your program's input and output into the provided text fields, then click "Load Data" and "Play".
You'll see Pacman and the ghost move according to your data, along with the current game state (win/lose/invalid).
You can also generate custom test cases by entering a seed number and clicking "Generate Input."
Note! The "invalid" status in the Pacman Simulation Visualizer does not check whether the ghost's movement path is valid.
(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 = '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.