# ZOJ 3420 Double Maze （BFS）

﻿﻿

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3420

#include <iostream>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define mem(a) memset(a,0,sizeof(a))
typedef long long ll;
const int N = 2000005;
const int M = 10005;
const ll mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-10;
using namespace std;

int T, n = 6;
struct MAZE {
int barr[7][7][5], hole[7][7];
int sx, sy, ex, ey;
} a, b;

MAZE INI() {
MAZE a;
int x, tmp;
for(int i = 0; i < 6; i++) {
for(int j = 0; j < 6; j++) {
cin >> x;
for(int k = 0; k < 4; k++) {
tmp = x & 1; x /= 2;
if(tmp) a.barr[i][j][k] = 1;
else a.barr[i][j][k] = 0;
}
tmp = x & 1; x /= 2;
if(tmp) a.hole[i][j] = 1;
else a.hole[i][j] = 0;

tmp = x & 1; x /= 2;
if(tmp) a.sx = i, a.sy = j;

tmp = x & 1;
if(tmp) a.ex = i, a.ey = j;

}
}
return a;
}
bool ok(int x, int y) {
if(x >= 0 && x < 6 && y >= 0 && y < 6) return 1;
return 0;
}
struct ST {
string ans;
int x1, y1, x2, y2;
};

string s = "DLRU";
int dx[] = {1, 0, 0, -1};
int dy[] = {0, -1, 1, 0};
int f[] = {1, 0, 2, 3};
int vis[7][7][7][7];
void solve(MAZE a, MAZE b) {
queue <ST> q;
ST x;
mem(vis);
x.x1 = a.sx;
x.y1 = a.sy;
x.x2 = b.sx;
x.y2 = b.sy;
x.ans = "";
q.push(x);
vis[a.sx][a.sy][b.sx][b.sy] = 1;
while(!q.empty()) {
ST cur = q.front(); q.pop();
if(cur.x1 == a.ex && cur.y1 == a.ey && cur.x2 == b.ex && cur.y2 == b.ey) {
cout << cur.ans << endl;
return;
}
for(int i = 0; i < 4; i++) {
int ax, ay, bx, by;
if(a.barr[cur.x1][cur.y1][f[i]] == 0) {
ax = cur.x1 + dx[i];
ay = cur.y1 + dy[i];
} else {
ax = cur.x1;
ay = cur.y1;
}
if(b.barr[cur.x2][cur.y2][f[i]] == 0) {
bx = cur.x2 + dx[i];
by = cur.y2 + dy[i];
} else {
bx = cur.x2;
by = cur.y2;
}

if(!ok(ax, ay) || !ok(bx, by)) continue;
if(vis[ax][ay][bx][by] || !a.hole[ax][ay] || !b.hole[bx][by]) continue;

vis[ax][ay][bx][by] = 1;
ST now;
now.x1 = ax;
now.y1 = ay;
now.x2 = bx;
now.y2 = by;
now.ans = cur.ans + s[i];
q.push(now);
}
}
cout << -1 << endl;
}

int main() {

//freopen("in.txt", "r", stdin);
cin >> T;
MAZE a = INI();
for(int ca = 1; ca < T; ca++) {
MAZE b = INI();
solve(a, b);
a = b;
}
return 0;
}