Problem: Probe
Want to try solving this problem? You can submit your code online if you log in or register.
Probe
Time Limit: 1 second
Memory Limit: 1 GB
Input File: probein.txt
Output File: probeout.txt
Earth is the only known planet to harbour life.
There are many planets out there that have some of the things
needed for life. Let me introduce you to one in particular, Kepler-442b.
Discovered early last year, it is the most Earth-like planet we know
about. Although a little bigger than Earth, the conditions
are almost perfect for life. Almost. It's missing liquid water.
The Australian Institute for Observing the Cosmos has just sent out a
massive probe full of water to crash into the planet. The water
will spill out on impact to plant the metaphorical seeds of life,
but the shock of the impact will also cause a fissure to form elsewhere,
which will spill lava.
Scientists have selected a small, empty desert for the probe which can
be represented by a grid of squares with R rows and C columns.
They happen to know exactly which square the probe will crash in and
also the square where the fissure will form.
The square where the probe crashes is instantly covered in water,
while the square where the fissure forms is instantly covered in lava.
As time passes, the water and lava spread out over the desert in a simple way.
Each minute:
- Any empty square that shares a side with a square covered in water will also become
covered in water.
- Any empty square that shares a side with a square covered in lava will also become
covered in lava.
- Any empty square that shares a side with both a square covered in lava and
one covered in water will form into rocky mountains (probably made of obsidian),
over which neither water nor lava will flow.
Lava and water never flow outside the desert.
You have been tasked with helping the scientists figure out what the desert will
look like after the water and lava finish flowing. You will be asked Q questions,
for each of which you must answer whether a given square will be covered in water, lava
or mountains.
Input
The first line of input will contain six integers (separated by spaces), R, C, rp, cp, rf and cf.
- R and C denote the number of rows and columns in the grid respectively.
Rows are labelled from 1 to R (from top to bottom) and columns are labelled from 1 to C (from left to right).
- The probe will crash in the square in the rpth row and cpth column.
- The fissure will form in a different square in the rfth row and cfth column.
The second line will contain a single integer
Q, the number of questions that will be asked.
Q lines follow, the
ith of which contains two integers
ri and
ci.
Output
You should output
Q lines. The
ith line should contain a single word describing
the state of the square in the
rith row and
cith column:
- LAVA if the square is covered in lava.
- WATER if the square is covered in water.
- MOUNTAINS if the square is covered in mountains.
You know for a fact that every square will eventually be covered by one of the above.
Sample Input 1
4 7 2 5 3 2
3
1 1
1 3
3 6
Sample Output 1
LAVA
MOUNTAINS
WATER
Sample Input 2
2 3 1 1 1 2
2
1 1
2 2
Sample Output 2
WATER
LAVA
Explanation
The two diagrams above show the state of the desert after the water and lava have finished flowing.
The fissure and the probe have been marked on the map for clarity.
Dark grey squares are covered in lava while light grey squares are covered in water. The striped squares
are mountains.
Subtasks & Constraints
For all subtasks, 1 ≤ R, C, Q ≤ 100000, 1 ≤ rp, rf, ri ≤ R and 1 ≤ cp, cf, ci ≤ C.
Additionally, the fissure will always form in a different square to the probe's landing spot.
- For Subtask 1 (20 marks), rp = 1, cp = 1, rf = R and cf = C.
That is, if your program correctly solves the problem when the probe is always in the
top-left corner and the fissure is always in the bottom-right corner, you will
receive 20 marks.
- For Subtask 2 (15 marks), R = 1.
- For Subtask 3 (25 marks), R, C ≤ 50.
- For Subtask 4 (20 marks), R, C ≤ 1000.
- For Subtask 5 (20 marks), there are no further constraints.