Person in Charge

• cq_irritater

Attention

This problem requires file I/O (honey1.in / honey1.out).

Problem Background

Sleeping Bear is an adorable little bear who becomes even cuter the more honey it eats. However, every time it goes to collect honey, it gets stung by bees all over its head. Today it wants to eat honey again, but it doesn't want to get stung, so it asks you to help design an escape route to avoid the bees' pursuit.

Problem Description

Given a positive integer $k$, representing a $k \times k$ map with characters B, X, R, and L indicating:

• B: Sleeping Bear's position (with bees right behind it by default);
• X: Impassable terrain;
• R: Passable road;
• L: Lake location (only by jumping into the lake can Sleeping Bear avoid bee stings).

Help Sleeping Bear find a path to the lakeside (it can move one cell up, down, left, or right each turn). Output Yes if such a path exists, otherwise output No.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, indicating the number of test cases.

For each test case:

• The first line contains an integer $k$, representing the size of the $k \times k$ map;
• The next $k$ lines each contain $k$ characters, describing the map's layout.

Output Format

For each test case, output one line with either Yes or No, indicating whether Sleeping Bear can escape the bees.

Sample

1
5
XXRRR
XRRRR
XXXXL
XXBRR
XXRRR

Yes

2
5
XXRRR
XRRRX
XXXXL
XXBRX
XXRRR
4
RRRR
XLXX
BXLR
RRLX

No
Yes

Sample 1 Explanation

Character G marks one possible escape route for Sleeping Bear:

XXRRR
XRRRR
XXXXL
XXBRG
XXGGG

Data Range

• For $50\%$ of cases: $1 \le T \le 10$, $2 \le k \le 10$
• For $100\%$ of cases: $1 \le T \le 10$, $2 \le k \le 1000$
• The map is guaranteed to contain only B, X, R, and L characters, with exactly one B.
• No guarantees are made about the number of Ls!

Official Solution

link