记一下
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <vector>
#include <queue>
#include <cassert>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 1010;
int T = 1, n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char ch[4] = {'U', 'R', 'D', 'L'};
char g[N][N];
bool st[N][N];
int dist[N][N];
PII pre[N][N];
int bfs()
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
dist[1][1] = 0;
deque<PII> q;
q.push_back({1, 1});
pre[1][1] = {1, 1};
while(q.size())
{
auto t = q.front();
q.pop_front();
int x = t.x, y = t.y;
if(x == n && y == m) return dist[x][y];
if(st[x][y]) continue;
st[x][y] = true;
for(int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 1 || a > n || b < 1 || b > m) continue;
int w = dist[x][y] + (g[x][y] != ch[i]);
if(w < dist[a][b])
{
dist[a][b] = w;
pre[a][b] = {x, y};
if(g[x][y] != ch[i]) q.push_back({a, b});
else q.push_front({a, b});
}
}
}
return -1;
}
int main()
{
cin >> T;
while(T--)
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> g[i] + 1;
cout << bfs() << endl;
int x = n, y = m;
while(x != 1 || y != 1)
{
auto [i, j] = pre[x][y];
int k = 0;
while (i + dx[k] != x || j + dy[k] != y) k++;
if (ch[k] != g[i][j])
cout << i << " " << j << " " << ch[k] << "\n";
x = i, y = j;
}
}
return 0;
}