Description

After clearing every dot and escaping the ghost, you thought the nightmare was over.
A strange voice echoes: “Nice try … now beat this.”
You are teleported into a fresh maze.
It still contains ordinary dots O, but now ten power‑dots X are spread across the map.
Whenever Pacman eats a power‑dot:

• The ghost immediately turns blue ( “frightened mode” ) for 10 rounds;
• During those 10 rounds it runs away from Pacman;
• If Pacman meets the blue ghost, the ghost is eaten, and the ghost will re‑spawn 10 rounds later on its initial square.

Survive all T rounds and reach the required score to escape safely back to your own world.

Task Implementation

You must modify the provided code at the two parts marked "TODO-01" and "TODO-02" to help Pacman evade the ghosts 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.

Ghost Movement Logic

(Already implemented; modifying it is not recommended)

In normal mode:

• Ghost has a 50% chance to move randomly to an adjacent cell.

• Ghost also has a 50% chance to move one step towards Pacman(Normal mode).

In Frightened mode:

• Move one step away from Pacman.

Ghost never remain stationary.

Important Notes

• 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."

Power Dot & Frightened Mode Rules

When pacman moves and may eat O/X :

• O(Normal dot) : disappears.
• X(Power dot) : disappears, and if no frightened mode is active, sets the frightened timer to 10 and counts as one frightened-mode trigger.
  • ​If Pacman eats additional X while the timer > 0, the timer will not be reset and no new triggers will be counted.

While the frightened timer > 0:

1. Ghost moves away from Pacman.

2. If Pacman lands on the blue ghost, ghost disappears and re-spawns after 10 rounds.

3. At end of each round timer--; when timer reaches 0 the surviving blue ghost reverts to normal.

There are exactly 10 power-dots in each test case.

Scoring

To pass each testcase , you should:

• Testcases 1 ~ 6: Clear all normal dot O. (The solution for the mid-2 practice problem will work)
• Testcases 7 ~ 8: Clear all normal dot O and trigger frightened mode at least 7 times. (see Hint)
• Testcases 9 ~ 10: Clear all normal dot O​, trigger frightened mode at least 7 times, and eat at least one blue ghost. (see Hint)

Constraints

• 1 ≤ N, M ≤ 25

• 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.

Subtasks

• Testcases 1 ~ 3: Except for the surrounding walls, no other grids are walls.
• Testcases 4 ~ 6: There is exactly one dot.
• Testcases 7 ~ 10: No additional restrictions.

Testing on Your Computer

• 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.

Code

#include <bits/stdc++.h>
using namespace std;

int T, R, C;
vector<string> grid;
int vis[100][100];

struct Position {
    int x, y;
    int operator-(const Position& other) const {
        return abs(x - other.x) + abs(y - other.y);
    }
    bool operator==(const Position& other) const {
        return x == other.x && y == other.y;
    }
};

class Entity {
    public:
        Entity(Position pos): pos(pos) {}
        virtual ~Entity() = default;
        virtual void move() = 0;
        Position getPosition() const {
            return pos; 
        }
    protected:
        Position pos;
};

class Pacman : public Entity {
    public:
        Pacman(Position pos): Entity(pos) {}

        void setGhostPos(const Position& pos) { 
            ghostPosition = pos;
        }

        void move() override {
            // TODO-01: Implement how Pacman moves in each round.
        }

    private:
        Position ghostPosition;
};

class Ghost : public Entity {
    public:
        Ghost(Position p): Entity(p), startPosition(p) {}

        void setPacmanPos(const Position& p) { 
            pacmanPosition = p; 
        }

        void setFrightened(bool f) { 
            frightened = f; 
        }

        void stateUpdate() {
            if (!alive) {
                if (--timer == 0) {
                    revive();
                }
                return;
            }
        }

        bool isAlive() const { 
            return alive; 
        }

        bool isFrightened() const { 
            return frightened && alive; 
        }

        void eaten() {
            alive = false;
            frightened = false;
            pos = {-1, -1};
            timer = 10;
        }

        void revive() {
            alive = true;
            frightened = false;
            pos = startPosition;
        }

        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++) {
                int nx = pos.x + dxs[i];
                int ny = pos.y + dys[i];
                if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
                if (grid[nx][ny] == '#') continue;
                nbrs.push_back({nx, ny});
            }
            if (nbrs.empty()) return;

            Position chosen = pos;
            double p = (double)rand() / RAND_MAX;
            if (p < 0.5) {
                int best = INT_MAX;
                for (auto &c : nbrs) {
                    int d = c - pacmanPosition;
                    if (d < best) {
                        best = d;
                        chosen = c;
                    }
                }
            } else {
                chosen = nbrs[rand() % nbrs.size()];
            }

            if (frightened) {
                int best = -1;
                for (auto &c : nbrs)
                    best = max(best, c - pacmanPosition);
                vector<Position> far;
                for (auto &c : nbrs)
                    if ((c - pacmanPosition) == best) far.push_back(c);
                chosen = far[rand() % far.size()];
            }

            pos = chosen;
        }

    private:
        Position startPosition, pacmanPosition;
        bool alive = true, frightened = false;
        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): frightenedTimer(0) {}

        void handlePacmanCell(const Position& pacman, Ghost& ghost) {
            if(!vis[pacman.x][pacman.y]) {
                if (grid[pacman.x][pacman.y] == 'O'){
                    vis[pacman.x][pacman.y] = 1;
                }
                else if (grid[pacman.x][pacman.y] == 'X'){
                    vis[pacman.x][pacman.y] = 1;
                    if(!ghost.isFrightened()) {
                        frightenedTimer = 10;
                        ghost.setFrightened(true);
                    }
                }
            }
        }

        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() && ghost.isFrightened()) {
                ghost.eaten();
            }
        }

    private:
        int frightenedTimer;
};

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    cin >> T >> R >> C;
    grid.resize(R);
    for (int i = 0; i < R; i++) cin >> grid[i];

    Position pacman_start, ghost_start;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            if (grid[i][j] == 'P') pacman_start = {i, j};
            if (grid[i][j] == 'G') ghost_start   = {i, j};
        }

    unsigned GHOST_SEED = /* TODO-02 */;
    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();
        gameMap.handlePacmanCell(pacman.getPosition(), ghost);
        gameMap.resolveCollision(pacman, ghost);

        ghost.setPacmanPos(pacman.getPosition());
        ghost.move();
        gameMap.resolveCollision(pacman, ghost);
        ghost.stateUpdate();
        gameMap.updateTimer(ghost);

        cout << pacman << ' ' << ghost << '\n';
    }

    cout << GHOST_SEED << '\n';
    return 0;
}

 

Pacman Simulation Visualizer

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: Output:

Input

(Input handling is already implemented in the provided code.)

The first line contains three integers N, M, and T, representing the dimensions of the maze ( N × M ) and the number of rounds T

The next N lines each contain M characters c_i,j , where:

• c_i,j = '#' represents a wall.

• c_i,j = '.' represents an empty space.

• c_i,j = 'O' represents a dot.

• c_i,j = 'X' represents a power dot.

• c_i,j = 'P' represents Pacman's initial position.

• c_i,j = 'G' represents a ghost's initial position.

Output

(Output handling is already implemented in the provided code.)

Output ( T+1 ) lines:

• For the first T lines, each line should contain four integers P_x, P_y, G_x, G_y, representing Pacman's position (P_x, P_y) and the ghost's position (G_x, G_y) 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.

Sample Input  Download

Sample Output  Download

Tags

Discuss