Buggy python submission (verdict: Runtime Error):
// C++11
#include "bits/stdc++.h"
#include <sys/time.h>
#include <emmintrin.h>
#include <string>
#include <sstream>
#include <fstream>
#include <random>
#include <bitset>

using namespace std;

inline long long GetTSC() {
  long long lo, hi;
  asm volatile ("rdtsc": "=a"(lo), "=d"(hi));
  return lo + (hi << 32);
}
inline double GetSeconds() {
  return GetTSC() / 2.8e9;
}

const long inf = pow(10,15);
int di[] = {-1,0,1,0};
int dj[] = {0,1,0,-1};
tuple<int, int>q[50*50*50*50];

void solve(){
  double starttime = GetSeconds();
  while(1){
    int w,h;
    cin >> w >> h;
    // cerr << w << ", " << h << endl;
    if(w==0 && h==0) break;
    int lp,ls,rp,rs;
    bool lb[2500] = {};
    bool rb[2500] = {};
    bool f[2500][2500] = {};
    for(int i=0; i<h; i++){
      string s;
      cin >> s;
      for(int j=0; j<w; j++){
        if(s[j]=='#') lb[i*w+j] = 1;
        if(s[j]=='%') lp = i*w+j;
        if(s[j]=='L') ls = i*w+j;
      }
      cin >> s;
      for(int j=0; j<w; j++){
        if(s[j]=='#') rb[i*w+j] = 1;
        if(s[j]=='%') rp = i*w+j;
        if(s[j]=='R') rs = i*w+j;
      }
    }
    f[ls][rs] = 1;
    int qi = 0;
    int qe = 1;
    q[0] = make_tuple(ls,rs);
    bool ff = 0;
    while(qi<qe){
      int lt = get<0>(q[qi]);
      int rt = get<1>(q[qi]);
      int li = lt / w;
      int lj = lt % w;
      int ri = rt / w;
      int rj = rt % w;
      qi++;
      // cerr << "qie: " << qi << ", " << qe << ", lij: " << li << ", " << lj << ", rij: " << ri << ", " << rj << endl;
      for(int i=0; i<4; i++){
        int nli = li + di[i];
        int nlj = lj + dj[i];
        int nri = ri + di[i];
        int nrj = rj - dj[i];
        if(nli < 0 || nli >= h || nlj < 0 || nlj >= w || lb[nli*w+nlj]){
          nli = li;
          nlj = lj;
        }
        if(nri < 0 || nri >= h || nrj < 0 || nrj >= w || rb[nri*w+nrj]){
          nri = ri;
          nrj = rj;
        }
        int nlt = nli*w+nlj;
        int nrt = nri*w+nrj;
        if(nlt == lp && nrt == rp){
          ff = 1;
          break;
        }
        if(nlt == lp || nrt == rp) continue;
        if(f[nlt][nrt]) continue;
        f[nlt][nrt] = 1;
        q[qe++] = make_tuple(nlt,nrt);
      }
      if(ff) break;
    }
    if(ff){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }
  // cerr << "time: " << GetSeconds() - starttime << endl;

  return;
}

int main() {
  solve();
  return 0;
}




Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        if n == 0:
            break
        a = [LS() for _ in range(n)]
        s = S()
        k = S()
        l = len(k)
        if s == k:
            rr.append(0)
            continue
        u = set([s])
        c = set([s])
        t = 0
        r = -1
        while c:
            t += 1
            ns = set()
            for cs in c:
                for d,e in a:
                    nt = cs.replace(d,e)
                    if len(nt) > l:
                        continue
                    ns.add(nt)
            if k in ns:
                r = t
                break
            c = ns - u
            u |= ns
        rr.append(r)

    return '\n'.join(map(str,rr))


print(main())