Problem Description

This problem is translated from CEOI 2024 Day 2 T1 “Toy”.

Ben, the problem setter of CEOI 2024, received a gift from the scientific committee—a toy. This toy is a puzzle. You can imagine it as a grid with $H$ rows and $W$ columns, with a metal object placed on it. The metal object consists of two parts: a horizontal part of size $1 \times K$ and a vertical part of size $L \times 1$. These two parts are loosely connected. Neither part can rotate, but they can slide horizontally or vertically within the grid, as long as they always overlap on one cell.

There are also some obstacles in the grid. No part of the metal object may pass through obstacles. Even worse, they also cannot move outside the grid (not even partially). Ben’s task is to move the metal object from the given starting position to a (possibly different) target position, such that the two parts overlap on the designated target cell.

However, Ben has been playing with this toy for quite some time and still has not solved the puzzle. In fact, he has started to suspect that the organizers are messing with him and gave him an unsolvable puzzle. Therefore, he asks for your help to determine whether this puzzle is solvable.

Input Format

The first line contains four space-separated integers $W, H, K, L$, denoting the width and height of the puzzle, the width of the horizontal part, and the height of the vertical part. The second line contains four integers $x_h, y_h, x_v, y_v$, denoting the coordinates of the top-left cell of the horizontal part and the top-left cell of the vertical part.

Rows are numbered from $0$ to $H - 1$ from top to bottom, and columns are numbered from $0$ to $W - 1$ from left to right. The $x$ coordinate denotes the column index, and the $y$ coordinate denotes the row index.

The next $H$ lines each contain $W$ characters describing the grid. The character . denotes an empty cell, the character X denotes an obstacle, and the character * denotes the target cell.

It is guaranteed that the initial position of the metal object is valid, i.e. the two parts overlap on one cell, and neither part overlaps any obstacle or goes outside the grid.

There is exactly one target cell, i.e. there is exactly one character * in the grid. It may overlap the initial position of the metal object.

Output Format

If it is possible to move the metal object to the target cell, output one line YES; otherwise, output NO.

4 3 2 2
0 1 0 0
.X.*
....
...X

YES

2 3 2 3
0 1 0 0
.X
.*
.X

NO

Hint

Sample Explanation 1

The initial state is as follows:

We can first move the vertical part down by one cell, and then alternate moving the horizontal part and the vertical part as much as possible until it can no longer continue. Next, we can move the vertical part up and to the right to reach the target cell, and finally move the horizontal part up to also reach the target cell.

Sample Explanation 2

It is impossible to move the vertical part without hitting an obstacle, so it can never reach the target cell.

For all input, the following Constraints hold:

• $2 \leq W, H \leq 1\,500$
• $2 \leq K \leq W, 2 \leq L \leq H$
• $0 \leq x_h \leq W - K, 0 \leq y_h \leq H - 1$
• $0 \leq x_v \leq W - 1, 0 \leq y_v \leq H - L$

The detailed additional constraints and scores for the subtasks are given in the table below.

Translated by ChatGPT 5