E. 方格迷宮 (maze)

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100 + 5;

const pair<int, int> dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int val[maxn][maxn], dis[maxn][maxn];

void bfs(int sx, int sy, int bit) {
    memset(dis, 0x3F, sizeof(dis)); /// INF
    if (val[sx][sy] >> bit & 1) return; /// can't even start
    dis[sx][sy] = 0;
    queue<pair<int, int>> que; que.emplace(sx, sy);
    while (!que.empty()) {
        auto [nx, ny] = que.front(); que.pop();
        /// only push if can update dis ///
        /// since using bfs, dis will never be updated twice ///
        for (auto [dx, dy] : dir) {
            if (dis[nx+dx][ny+dy] != dis[0][0] or ((val[nx+dx][ny+dy] >> bit) & 1)) continue;
            dis[nx+dx][ny+dy] = dis[nx][ny] + 1;
            que.emplace(nx+dx, ny+dy);
        }
    }
}

void solve() {
    int N, M; cin >> N >> M;

    memset(val, 0xFF, sizeof(val)); /// -1, set all bits to 1
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) cin >> val[i][j];
    }

    int x0, y0, x1, y1; cin >> x0 >> y0 >> x1 >> y1;

    int ans = 0;
    for (int bit = 29; bit >= 0; --bit) {
        bfs(x0, y0, bit);
        if (dis[x1][y1] != dis[0][0]) { /// dis[0][0] is always INF
            /// if (x0, y0) is able to walk to (x1, y1) without having `bit`-th bit be 1 ///
            /// then we can just discard those grid forever (by setting every bit to 1) ///
            for (int i = 1; i <= N; ++i) {
                for (int j = 1; j <= M; ++j) {
                    if (dis[i][j] == dis[0][0]) val[i][j] = val[0][0]; /// val[0][0] is always all 1
                }
            }
        }
        else {
            /// must have `bit`-th bit be 1 ///
            ans |= (1 << bit);
        }
    }
    bfs(x0, y0, 31); /// can walk if not discarded

    /// back-tracking to find answer ///
    string command = "";
    int nx = x1, ny = y1;
    while (nx != x0 or ny != y0) {
             if (dis[nx-1][ny] < dis[nx][ny]) --nx, command += "D";
        else if (dis[nx+1][ny] < dis[nx][ny]) ++nx, command += "U";
        else if (dis[nx][ny-1] < dis[nx][ny]) --ny, command += "R";
        else if (dis[nx][ny+1] < dis[nx][ny]) ++ny, command += "L";
        else exit(-1); /// why here ???
    }
    reverse(begin(command), end(command));

    cout << ans << " " << dis[x1][y1] << "\n";
    cout << command << "\n";
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int t; cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}