Submit | All submissions | Best solutions | Back to list |
AHORCADO - B Beware, the end of the world |
The end of the world always has been a subject of controversy thru history, for example, in year 999 and in the 1999. Now there are persons that believe that the Mayan predicted a change in 2012, specifically in 21st December, 2012, some other speculate that the EoW will come with certain asteroid crashing onto Earth, or that planetary aligning has something to do with it....
At ACM (Association of Catastrophe Mitigation) they are 100% sure that the end might come with a Zombie Apocalypse, accordingly they are preparing with a Zombie Detection Mechanism, that it is some sort of radar. Right now the mechanism is on beta testing because is having errors identifying zombies. Sometimes it gives false positives measures. They have asked you, a wonderful programmer, to make a program that tells them if a lecture is right or not, basically you will be given two 2-D snapshots of zombies locations, let's call them the previous and the present snapshots, the zombies will be represented by a '*', while empty spaces will be represented by '.', your awesome program must tell if the present snapshot is a valid one, based on the previous one. A present snapshot is considered valid if:
- It has no less zombies than the previous snapshot.
- Every zombie in the previous snapshot could have moved only one square in each of the eight directions, or it is in the same square it was previously.
Input
The first line will have the dimensions of the snapshots, in the form of R C. (2 ≤ R, C ≤ 20)
Then R lines of C characters follow, describing the previous snapshot, then another set of R lines and C characters each line, that belongs to the present snapshot. The two snapshots are separated by a line with the character 'N'.
The last test case is followed by 0 0.
There will be at most 9 zombies in previous snapshot.
Output
For each test case print VALID, if the two snapshots correspond each other, NOT VALID otherwise.
Example
Input: 5 4
....
....
.*..
....
....
N
....
....
..*.
....
....
6 6
......
.*..*.
......
......
......
......
N
......
....*.
......
....*.
......
..*...
0 0
Output:
VALID
NOT VALID
Added by: | Olson Ortiz |
Date: | 2011-07-27 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C CSHARP C++ 4.3.2 CPP JAVA |
Resource: | Used in 3ra Olimpiada de Programación PUCMM-ACM-ISC in december/2012 |
hide comments
2022-03-16 13:12:00 Sushovan Sen
Does the map wrap around? |
|
2015-07-11 15:12:19 Rishav Goyal
A very nice problem :D |
|
2013-05-12 05:31:36 BLB
can there be extra zombies in the 2nd snapshot? |
|
2013-05-02 11:59:34 mala da.... annamala
So, according to this 4 4 .... .... .... *.*. N .... ...* .... .*.., is valid? |