Descend to Hell

0

0 votes
Easy
Problem

You are walking on a rectangular grid(which is the upper floor of hell) of size n*m. Each cell is either intact(perfect) or it is cracked. From each cell you can move to cells that are side-adjacent with yours(you cannot make jumps on the same cell). If you move to a cracked cell, then you fall through it and if you move to an intact cell, then it becomes cracked.

You are initially at a cracked cell(r1, c1) and you need to fall down and descend to hell through the cell (r2, c2)(Descending through other cells may result in encounter with monsters) . Can you do it?

INPUT

First line of input contains t , the number of test cases. Each test case contains two integers, n and m (1 ≤ n, m ≤ 500) — the number of rows and columns in the grid description.

Each of the next n lines describes the initial state of the level of the grid, each line consists of m characters "." (that is, intact cell) and "X" (cracked cell).

The next line contains two integers, r1 and c1 (1 ≤ r1 ≤ n, 1 ≤ c1 ≤ m) — your initial coordinates. It is guaranteed that the description of the grid contains character 'X' in cell (r1, c1), that is, the starting cell is initially cracked.

The next line contains two integers r2 and c2 (1 ≤ r2 ≤ n, 1 ≤ c2 ≤ m) — the coordinates of the cell through which you need to fall. The final cell may coincide with the starting one.

OUTPUT

For each test case, output "YES" if you can descend to hell. Else output "NO"

CONSTRAINTS

1t100

1n500

1m500

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first sample test one possible path is:

(1,6) -> (2,6) -> (3,6) -> (4,6) -> (4,5) -> (4,4) -> (4,3) -> (4,2) -> (4,1) -> (3, 1) -> (2,1) -> (2,2) -> (2,3) -> (1,3) -> (1,2) -> (2,2)

After the first visit of cell (2, 2) it cracks and when you step there for the second time, you fall through that cell and descend to hell.

Editor Image

?