Penny-pinching

University of Oregon (UO), like most colleges in the United States (and
Catalonia, I guess), is not exactly flush with cash. To save as much
money as possible, professors not only have to teach and research and
publish and organize responsible sports parties for their students — but
now they also have to make sure all the lights in the college buildings
are turned off before going back home.

However, this is not an easy task. In order to (again) save money, UO
buildings only have exactly one switch per doorway. The switch is either
on the right side (east) of a room, or in the bottom side (south) of a
room. By pressing it, you will switch the lights of both rooms connected
by the doorway. For example, in the following building, where ‘X’ means
a room with the lights off, ‘O’ a room with the lights on, and ‘.’ an
empty space,

    O..X
    XXXO
    ..X.

it is possible to turn off all the lights. For instance, we can first
press the switch in the doorway below the room in position (1,1), that
is, the room in the first row and first column of the map:

    X..X
    OXXO
    ..X.

Then, we can press the switch in the doorway to the right of the room in
position (2,2):

    X..X
    OOOO
    ..X.

And finally, we can turn off all the lights by pressing the switch to
the right of the rooms in positions (2,1) and (2,3):

    X..X
    XXXX
    ..X.

Tadaaaa! Another 14 cents saved. Five more years doing this and we will
be able to pay the administrative team that oversees the overworked
professors doing this important job.

Unfortunately, it is not always possible to turn off all the lights. For
instance, on the following campus with four disconnected buildings,

    ...OX...O
    .OXX.XXXO
    ..X....O.
    X..OXO.X.

it turns out that it is possible to turn off all the lights of three of
the four buildings, but not the fourth one.

Given a map of a UO campus, can you tell whether it is actually possible
to turn off all lights? If so, can you provide a way?

Input

Input consists of several descriptions of campus maps. Each one begins
with the number of rows n and the number of columns m (both between 1
and 400), followed by n lines with m characters each, describing the
rooms of the campus as explained above. Assume that every map contains
at least one room.

Output

Print a line for each case. If it is impossible to turn off all the
lights, just print “NO”. Otherwise, print “YES” followed by a list of
switch presses that, when executed in the given order, will turn off all
the lights. A switch press is a triplet i j d where i and j are the
(1-indexed) row and column of a room, and d is either ‘R’ (right
doorway) or ‘B’ (doorway below). Values in a triplet are separated by a
single space, while “YES” and switch presses are separated by double
spaces.

There might be many ways to turn off the lights. We will accept any one
as long as you do not press the same switch twice or more.

Problem information

Author: Omer Gimenez
Event: Vint-i-quatrè Concurs de Programació de la UPC - Final
Date: 2026-10-07

Generation: 2026-10-05T09:10:35.553Z

© Jutge.org, 2006–2026.
https://jutge.org
