Prison Break

A prison has been built as a labyrinth.

The labyrinth is composed of huts labelled + or *. If you are in a hut +, you can only move to another hut + near your hut. One hut is considered near another one if the two huts have a side in common. If you are in a hut *, you can only move to another hut * near your hut.

The labyrinth can be considered as a rectangle of huts of width W and length L. W and L are integers. A hut is identified by its position on the horizontal side and vertical side of the labyrinth.

In this prison, all huts are “entry huts”, but there is only one “exit hut”. Given the labyrinth, the hut of the prisoner (called entry hut) and the exit hut, your task is to determine if the prisoner can escape.

In the example of Prison A (a labyrinth of length 4 and width 2), the prisoner can escape. In the second example (a labyrinth of length 3 and width 2), the prisoner cannot escape.

Prison A

Prison B

Input Specification

The first line of the input contains a single integer P, which is the number of data sets that follow. Each data set begins with a single line made up of 6 natural numbers in the form L W A B C D, where

• L is the length of the labyrinth, and W is the width of the labyrinth;
• A is the horizontal position of the prisoner's entry hut, and B is the vertical position of the entry hut;
• C is the horizontal position of the exit hut, and D is the vertical position of the exit hut.

This line is followed by W lines, each containing L characters. Each character will be + or *.

Output Specification

For each prison, print “YES” in a single line if the prisoner can escape, and “NO” if not.

Sample Input

1. 2
2. 4 2 1 2 4 1
3. ++**
4. *+++
5. 3 2 2 2 3 1
6. +*+
7. *+*

download as text file

Output for Sample Input

1. YES
2. NO

download as text file