Description

As a computer science student, one day you wake up and find yourself trapped inside the world of Pacman! You're stuck in a maze ( N × M ), relentlessly pursued by ghosts. Your mission is to eat all the dots scattered around the maze without being caught by the ghosts. Only after successfully clearing the dots can you escape safely back to your own world.

Task Implementation

You must modify the provided code at each part marked "TODO" 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)

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

• Ghost also has a 50% chance to move one step towards 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."

Constraints

• 1 ≤ N, M ≤ 20

• 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: Ensures that ghost cannot touch pacman.
• Testcases 4 ~ 6: Except for the surrounding walls, no other grids are walls.
• Testcases 7 ~ 8: There is exactly one dot.
• Testcases 9 ~ 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;

struct Position {
    int x, y;
    int operator-(const Position& other) const {
        // TODO-01: 
        // Return the Manhattan distance between two coordinates (i.e., the sum of the differences of their x and y coordinates).
    }
};

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-02:
            // Implement how Pacman moves in each round.
        }
    private:
        // TODO (optional):
        // You can add some extra code 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++) {
                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;
            if (!nbrs.empty()) {
                double p = (double)rand() / RAND_MAX;
                if (p < 0.5) {
                    int best = INT_MAX;
                    for (Position& c : nbrs) {
                        int d = c - pacmanPosition;
                        if (d < best) {
                            best = d;
                            chosen = c;
                        }
                    }
                } 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;
}

// TODO (optional):
// You can add some extra code here.

class GameMap {
    public:
        GameMap(const vector<string>& g) {
            // TODO-03:
            // Store the dots from the map.
        }
        void eatDot(const Position& p) {
            // TODO-04:
            // Make Pacman eat the dot at his current position (if there is one).
        }
};

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-05: */ ;
    // 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();
        gameMap.eatDot(pacman.getPosition());
        ghost.setPacmanPos(pacman.getPosition());
        ghost.move();
        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 = '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