题目描述
blablabla
记录方案
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
#define x first
#define y second
const int N = 2e3+10;
char g[N][N];
int t;
int n,m;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
bool st[N][N];
typedef pair<int,int> PII;
int dist[N][N];
string res;
pair<pair<int,int>,char> qq[N][N];
void print()
{
int x = n - 1,y = m - 1;
while(x || y)
{
res += qq[x][y].second;
PII t = qq[x][y].first;
x = t.x,y = t.y;
}
reverse(res.begin(),res.end());
cout << res << endl;
}
int bfs()
{
queue<PII> q;
q.push({0,0});
dist[0][0] = 0;
while(q.size())
{
auto t = q.front();
q.pop();
//int sx = t.x,sy = t.y;
for(int i = 0;i<4;i++)
{
int sx = t.x + dx[i],sy = t.y + dy[i];
if(sx<0||sx>=n||sy<0||sy>=m) continue;
if(g[t.x][t.y] == g[sx][sy]) continue;
if(st[sx][sy]) continue;
dist[sx][sy] = dist[t.x][t.y] + 1;
q.push({sx,sy});
st[sx][sy] = true;
if(dx[i]==-1)
{
qq[sx][sy] = {t,'U'};
}
if(dy[i]==1)
{
qq[sx][sy] = {t,'R'};
}
if(dx[i]==1)
{
qq[sx][sy] = {t,'D'};
}
if(dy[i]==-1)
{
qq[sx][sy] = {t,'L'};
}
if(sx==n-1&&sy==m-1) return dist[sx][sy];
}
}
return -1;
}
int main()
{
cin >> t;
while(t--)
{
res.clear();
memset(st,0,sizeof st);
cin >> n >> m;
for(int i = 0;i<n;i++) cin >> g[i];
int t = bfs();
if(t == -1) puts("-1");
else
{
cout << t << endl;
//print();
int x = n - 1,y = m - 1;
while(x || y)
{
res += qq[x][y].second;
PII t = qq[x][y].first;
x = t.first,y = t.second;
}
reverse(res.begin(),res.end());
cout << res << endl;
}
}
return 0;
}