Adult Shark
Time limit1sMemory limit512 MB
Simulate a grid of sharks that each move by fixed directional priorities, leave fading scent trails, and eat the weaker shark when they collide, until only shark 1 is left.
- Level
Medium7 of 10
- Topics
- Simulation, Implementation, Brute force, Array
- Solved
- No attempts yet
Problem
Teenage Shark has grown further and become an adult shark. Fish no longer come to the space where sharks live, and only other sharks remain. Each shark has a natural number between 1 and M, and all numbers are distinct. The sharks try to drive out the other sharks to hold their territory, and the adult shark numbered 1 is the strongest, so it can drive out all the rest.
M of the cells in an N×N grid each contain one shark. At the very start, every shark spreads its own scent on its own cell. After that, every second all sharks move simultaneously to one of the cells adjacent up, down, left, or right, and spread their scent on that cell. A scent disappears after the shark moves k times.
When a shark decides its movement direction, it first picks the direction of a cell among the adjacent cells that has no scent at all. If there is no such cell, it picks the direction of a cell that has its own scent. There may be several possible cells, and in that case the shark follows a specific priority. The priority may differ from shark to shark, and even for the same shark it may differ depending on the direction the shark is currently facing. The direction a shark faces at the very start is given as input, and after that, the direction it just moved in becomes the direction it faces.
After all sharks move, if several sharks remain in one cell, all of them are driven out of the grid except the shark with the smallest number.
Write a program that finds how many seconds it takes until only shark 1 remains in the grid when this process repeats.
Input
The first line gives N, M, and k. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)
From the next line, N lines give the appearance of the grid. 0 is an empty cell, and a nonzero number x means a cell containing shark x.
The next line gives the direction of each shark in order. 1, 2, 3, and 4 mean up, down, left, and right, respectively.
From the next line, the direction priorities of each shark are given in order, four lines per shark. Each line consists of 4 numbers. Of the four lines representing one shark, the first line is that shark's direction priority when it faces up, the second line is the priority when it faces down, the third line is the priority when it faces left, and the fourth line is the priority when it faces right. In each priority, the natural numbers from 1 to 4 each appear once. The direction that appears first has the highest priority. For example, if the priority is 1 3 2 4, the order of directions is up, left, down, right.
At the very start, every shark has an adjacent empty cell. Therefore, no shark is unable to move from the start.
Output
Print the time it takes until only shark 1 remains in the grid. If other sharks remain in the grid after more than 1,000 seconds, print -1.