Mirror Cave http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2153

aoj2153.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto x : v){cout << x << " ";} cout << endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(vv) for(auto v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
// typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

typedef tuple<int, int, int, int> TUPLE;

const int MAX_H = 52;
const int MAX_W = 52;
bool done[MAX_H][MAX_W][MAX_H][MAX_W];
vector<vector<string>> s;
int H, W;
vector<int> sx(2), sy(2), gx(2), gy(2);

// N, E, S, W
// kagamiawase
const int dx[2][4] = {
    {-1,  0,  1,  0},
    {-1,  0,  1,  0}
};
const int dy[2][4] = {
    { 0,  1,  0, -1},
    { 0, -1,  0,  1}
};

bool bfs() {
    queue<TUPLE> que;
    que.emplace(sx[0], sy[0], sx[1], sy[1]);
    done[sx[0]][sy[0]][sx[1]][sy[1]] = true;
    while (!que.empty()) {
        int x0, y0, x1, y1;
        tie(x0, y0, x1, y1) = que.front(); que.pop();
        if (x0 == gx[0] && y0 == gy[0] && x1 == gx[1] && y1 == gy[1]) return true;
        rep(k, 4) {
            int nx0 = x0 + dx[0][k];
            int ny0 = y0 + dy[0][k];
            int nx1 = x1 + dx[1][k];
            int ny1 = y1 + dy[1][k];

            if ((nx0 == gx[0] && ny0 == gy[0]) ^ (nx1 == gx[1] && ny1 == gy[1])) {
                continue;
            }

            if (!done[nx0][ny0][nx1][ny1] && s[0][nx0][ny0] == '.' && s[1][nx1][ny1] == '.') {
                que.emplace(nx0, ny0, nx1, ny1);
                done[nx0][ny0][nx1][ny1] = true;
            } else if (!done[nx0][ny0][x1][y1] && s[0][nx0][ny0] == '.' && s[1][nx1][ny1] == '#') {
                que.emplace(nx0, ny0, x1, y1);
                done[nx0][ny0][x1][y1] = true;
            } else if (!done[x0][y0][nx1][ny1] && s[0][nx0][ny0] == '#' && s[1][nx1][ny1] == '.') {
                que.emplace(x0, y0, nx1, ny1);
                done[x0][y0][nx1][ny1] = true;
            }
        }
    }
    return false;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t = 0;
    while (cin >> W >> H, W) {
        H += 2;
        W += 2;

        s.clear(); s.resize(2, vector<string>(H, string(W, '#')));
        rep2(i, 1, H - 1) {
            rep(b, 2) {
                cin >> s[b][i];
                s[b][i] = "#" + s[b][i] + "#";
            }
        }

        rep(b, 2) {
            rep(i, H) {
                rep(j, W) {
                    if (s[b][i][j] == (b ? 'R' : 'L')) {
                        sx[b] = i, sy[b] = j;
                        s[b][i][j] = '.';
                    }
                    if (s[b][i][j] == '%') {
                        gx[b] = i, gy[b] = j;
                        s[b][i][j] = '.';
                    }
                }
            }
        }

        rep(x0, H) rep(y0, W) rep(x1, H) rep(y1, W) done[x0][y0][x1][y1] = false;
        cout << (bfs() ? "Yes" : "No") << endl;
    }

}