RT

拜谢各位大佬 orz

蒟蒻代码如下：

#include <bits/stdc++.h>

namespace drest {
#define fcfo friend const fast_io& operator
#define defio const fast_io& io
#define gc1(_ch) (bool) ((_ch=getchar())==' '||_ch=='\n'||_ch=='\t'||_ch==4)
#define gc2(_ch) (bool) ((_ch = getchar())<'0'||_ch>'9')
    /* code by Drest */
	using std::string;	using std::pair;	using std::map;		using std::set;
	using std::vector;	using std::queue;	using std::deque;   using std::priority_queue;
	using std::sort;    using std::swap;	using std::min;	    using std::max;
	using std::floor;   using std::ceil;    char ch;
	template<class T> T abs(T x) {return x < 0 ? -x : x;}
	class fast_io {
		template<class T> static const fast_io& input_integer(defio, T &x) {
			T f = 1, res;   while(gc2(ch)) if(ch=='-') f = -1;  res = ch^48;
			while(!gc2(ch)) res=(res<<1)+(res<<3)+(ch^48);  x = res * f;	return io;
		}
		template<class T> static const fast_io& output_integer(defio, T &x)
		{if(x<0)putchar('-'); x = abs(x); if(x>9)io<<(T)(x/10); putchar(x%10+'0'); return io;}
		fcfo >> (defio, bool &x) 	    {return input_integer(io, x);}
		fcfo >> (defio, short &x) 		{return input_integer(io, x);}
		fcfo >> (defio, int &x)     	{return input_integer(io, x);}
		fcfo >> (defio, long &x) 		{return input_integer(io, x);}
		fcfo >> (defio, long long &x)	{return input_integer(io, x);}
		fcfo << (defio, short x)		{return output_integer(io, x);}
		fcfo << (defio, int x)	    	{return output_integer(io, x);}
		fcfo << (defio, long x)	    	{return output_integer(io, x);}
		fcfo << (defio, long long x)  	{return output_integer(io, x);}
		fcfo >> (defio, float &x)	    {scanf("%f", &x);   return io;}
		fcfo >> (defio, double &x)   	{scanf("%lf", &x);  return io;}
		fcfo << (defio, float x)      	{printf("%f", x);   return io;}
		fcfo << (defio, double x)     	{printf("%lf", x);  return io;}
		fcfo >> (defio, char &x) 	    {while(gc1(x)){}    return io;}
		fcfo << (defio, char x)       	{putchar(x);	    return io;}
		fcfo >> (defio, string &x)    	{while(gc1(ch)){}   x = ch; while(!gc1(ch)) x += ch; return io;}
		fcfo << (defio, string x)	  	{for(int i=0;i<x.size();i++)putchar(x[i]); return io;}
		fcfo >> (defio, char* &x)     	{string res; io >> res;  x=&res[0]; return io;}
		fcfo << (defio, char* x)	    {for (int i=0;i<strlen(x);i++) putchar(x[i]); return io;}
	public:
	  fast_io& getline(string &x) {x = ""; while ((ch = getchar()) != '\n' && ch != 4) x += ch; return *this;}
	  fast_io& getline(char* &x)  {string res;     this->getline(res);     x = &res[0];	  return *this;}
	};
	fast_io io, cin, cout;  const char & endl = '\n';
}
using namespace drest;
const int maxn = 2e3 + 10;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const char going[4] = {'U', 'D', 'L', 'R'};
bool ma[maxn][maxn];
int vis[maxn][maxn];
int n, m;
struct node {
    int x, y;
    int points;
    vector<char> g;
};
node bfs(int visnum) {
    queue<node> q;
    q.push({1,1,0});
    node ans = {-1, -1, 0x7f7f7f7f};
    while (!q.empty()) {
        node t = q.front();
        q.pop();
        if (t.x == n && t.y == m) {
            if (ans.points > t.points) ans = t;
            return t;
        }
        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i];
            int y = t.y + dy[i];
            if (x < 1 or x > n or y < 1 or y > m) continue;
            if (vis[x][y] == visnum) continue;
            if (ma[t.x][t.y] == ma[x][y]) continue;
            vis[x][y] = visnum;
            t.g.push_back(going[i]);
            q.push({x, y, t.points + 1, t.g});
            t.g.pop_back();
        }
    }
    return ans;
}
signed main() {
    int t;
    io >> t;
    while (t--) {
        io >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char p;
                io >> p;
                if (p == '0') ma[i][j] = false;
                else ma[i][j] = true;
            }
        }
        node re = bfs(t + 1);
        if (re.x == -1) {
            io << -1 << '\n';
        } else {
            io << re.points << '\n';
            for (char i : re.g) {
                io << i;
            }
            io << '\n';
        }
    }
    return 0;
}