CATM - The Cats and the Mouse

In a rectangular field of size n by m squares there is a mouse and two cats. The mouse is the first to make a move, then each of the cats makes a move, then again its the mouse's turn, and so on. In each move both the mouse and the cats can move exactly one square vertically or horizontally. If the mouse is standing at the edge of the field then in its next move it can jump off the field and is saved from the cats. If in the next move one of the cats moves to the field with the mouse then there is no escape for the mouse ... =(

You are to write a program which, knowing the initial positions of mouse and the two cats, will find out if there is any way for the mouse to escape from the cats, assuming of course that each cat will do its best to catch the mouse.


In the first line of input two integers n and m are given, not exceeding 100, where n is the number of rows, and m - the number of columns. The second line contains a number k [k <= 10], which defines the number of test cases for the given field. In the next k lines the initial positions of the mouse and the cats are given. The position in the field is given by two numbers: the first is the number of the row, the second is the number of the column. The first two integers are the coordinates of the mouse, the next four integers are the coordinates of the cats.


You must output k lines with answers for each test case. The answer is YES, if the mouse can escape or NO otherwise.


5 3
2 2 1 1 3 3
2 3 1 3 5 2
3 2 1 2 4 3


Author: Filimonenkov D.O.

hide comments
s_a_k_s_h_a_m: 2018-06-26 19:58:39

just calculate minimum distance required for mouse and both the cats to reach edge vertces
if mouse can reach earlier than both the cats for any edge vertex then it is safe
can be done in O(n+m) no need of bfs use formula -> dist = |x1-x2|+|y1-y2|

jmr99: 2018-06-06 14:37:06

pls someone explain !!!
or hint at least.

Last edit: 2018-06-06 14:37:41
ankur314: 2018-05-20 07:30:35

Can anyone explain the logic behind mouse being between diagonal? How can we say for sure that there will be no case providing a contradiction? spoj just checks for a few test cases...

spa1ish: 2018-05-01 16:18:14

@vivek_prime also make sure that mouse is in between two cats

beinghemendra: 2018-04-25 17:34:38

AC in one go <3

sharif ullah: 2018-01-02 20:08:25

its adhoc;
think in terms of square,,,,,
draw square,,,,&& put mouse inside the square,,,observe the position in which mouse make any of 4 moves it caught by cats

yashgulani: 2017-11-07 20:27:17

The bfs approach that comes in mind can be simply optimised through mathematics in o(m+n).
Don't think complex . Solve as if it Codeforces B problem

amulyagaur: 2017-11-04 21:13:22

AC in 1 GO :))) :P

dwij28: 2017-09-24 13:39:20

Don't know about elegance but it's simple 3xBFS :)

rc_4594: 2017-07-26 14:56:37

@vivek_prime consider the positions of mouse and cats and try again

Added by:Roman Sol
Time limit:0.158s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ZCon 2007