Expansion Game
Time limit2sMemory limit512 MB
Simulate multiple players expanding castles across a grid by up to S_i steps per turn until no one can move; report final castle counts.
- Level
Medium7 of 10
- Topics
- BFS, Graph, Simulation, Implementation
- Solved
- No attempts yet
Problem
Gusagwa and his friends are about to play a game of expansion. The game is played on a grid of size N×M, and each cell is either empty or blocked. Each player owns at least one castle, and these castles are also on the grid. No cell contains more than one castle.
The game runs in rounds, and in each round every player must expand their castles when their turn comes. Player 1 expands first, then player 2 expands, and the rounds continue this way.
On each turn, the player expands the castles they own into empty cells. Player i simultaneously builds a castle in every cell reachable by moving up to Si cells from any of their castles. Movement is allowed only between cells adjacent vertically or horizontally, and a move cannot enter a wall or a cell occupied by another player's castle. Once the player finishes building castles, the next player takes a turn.
The game ends when no player can expand any further. Given the initial state of the board, find the final state.
Input
The first line gives the grid dimensions N and M and the number of players P. The second line gives S1, S2, ..., SP.
The next N lines give the state of the board. '.' is an empty cell, '#' is a wall, and '1', '2', ..., '9' are the castles of each player.
Every player owns at least one castle, and no castle belongs to a player who is not in the game.
Output
Print the number of castles owned by player 1, player 2, ..., player P, separated by spaces.
Constraints
- 1 ≤ N, M ≤ 1,000
- 1 ≤ P ≤ 9
- 1 ≤ Si ≤ 109