Person in Charge

• 035966_L3

Attention

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

Problem Background

Sleeping Bear is an adorable little bear who becomes even cuter the more honey it eats. However, every time it collects honey, bees sting its head all over. Today it wants to eat honey again but hopes to avoid getting stung, so it asks you to help design an escape route to evade the bees' pursuit.

Problem Description

Given a positive integer $k$, representing a $k \times k$ map with characters:

• B: Sleeping Bear's position (bees are 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).

Known conditions:

• B positions should be treated as R positions.
• Sleeping Bear may start from any R position.
• Sleeping Bear can face any initial direction (up, down, left, right) when escaping.
• Each move, Sleeping Bear can either:
  • Move forward one cell in its current facing direction.
  • Turn left ( $90^\circ$ counter-clockwise) then move forward one cell.
  • Note: Sleeping Bear cannot turn around or turn right.
• A R position is considered safe if Sleeping Bear can reach any L position from it.

Determine which positions are safe.

Input Format

Multiple test cases.

First line: integer $T$ - number of test cases.

For each test case:

• First line: integer $k$ - map size;
• Next $k$ lines: $k$ characters each representing the map.

Output Format

For each test case, output $k$ lines of $k$ characters:

• Replace safe R positions with L;
• Replace unsafe R positions with X;
• Treat B positions as R positions;
• Keep original L and X characters unchanged.

Sample

1
5
XXRRR
XRRRR
XXXXL
XXBRR
XXRRR

XXXXL
XXXXL
XXXXL
XXLLL
XXLLL

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

XXXXX
XXXXX
XXXXL
XXXXX
XXXXX
XLLL
XLXX
LXLL
LLLX

Sample 1 Explanation

For example, the B position is safe because escape routes exist.

When facing right, the G marks its only escape path:

XXRRR
XRRRR
XXXXL
XXBGG
XXRRR

When facing left, one possible escape route (marked by G):

XXRRR
XRRRR
XXXXL
XXBRG
XXGGG

Actually, it could also make multiple loops in the bottom-right $4$ cells.

When facing down, both above routes are possible.

When facing up, escape becomes impossible.

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$
• Map contains only B, X, R, L, with exactly one B.
• No guarantees about the number of Ls!

Official Solution

link