题目大意
机器人站在一个$n\times m$大小的矩阵上，每个单元格都写有’L’、’R’、’U’和’D’当中的某一字符，表示机器人在此格移动方向——分别为左、右、上和下。
当走出矩阵或者走到已经访问过的单元格时停止移动。问，机器人从哪个单元格出发能移动的步数最多，输出单元格的坐标以及最大数量的步数。
解题思路
翻译一下题意即为，给定一个有向图，每个点的权值为$1$，且每个点只有一条出边，从某个点出发，每个点只能经过一次，求从何处出发所经过点的权值和最大，并求出最大值。
那么直接枚举每个点进行记忆化搜索即可，考虑到有环的存在，可以开个数组记录当前点的状态，如：$0$表示未被搜索到，$1$表示正在被搜索中，$2$表示已经被搜索过了。那么如果我们在搜索中遇到了状态为$1$的点就意味着碰到环了，此时记录一下环的大小即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <bits/stdc++.h>
#define maxn 4000100
typedef __int128_t int128;
using namespace std;
const double eps=1e-8;
int e[maxn],v[maxn],state[maxn];
int l=0,r=0;
inline int dfs(int x){
if(state[x]==2) return v[x];
if(state[x]==1){
int cur=1,u=e[x];
while(u!=x) ++cur,state[u]=2,u=e[u];
u=e[x];
while(u!=x) v[u]=cur,u=e[u];
state[x]=2; v[x]=cur;
return v[x];
}
state[x]=1;
dfs(e[x]);
if(state[x]!=2) v[x]=v[e[x]]+1,state[x]=2;
return v[x];
}
void solve(){
l=r+1; state[0]=2;
int n,m,ans=0,res=0;
cin >> n >> m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
++r;
char x; cin >> x;
if(x=='L'&&j!=1) e[r]=r-1;
if(x=='R'&&j!=m) e[r]=r+1;
if(x=='U'&&i!=1) e[r]=r-m;
if(x=='D'&&i!=n) e[r]=r+m;
}
}
for(int i=l;i<=r;++i){
if(ans<dfs(i)) ans=v[i],res=i-l+1;
}
cout << (res-1)/m+1 << ' ' << (res-1)%m+1 << ' ' << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t; cin >> t;
while(t--){
solve();
}
return 0;
}
|
此外，还可以在$dfs$前把所有环找出来。不过这种做法较上一种做法效率较低，而且还碰到了某些$ub$错误(C++17能过，C++20不能过，，)。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <bits/stdc++.h>
#define maxn 2010
using namespace std;
const double eps=1e-8;
char g[maxn][maxn];
int v[maxn][maxn];
bool vis[maxn][maxn];
int n,m;
inline void check(int x,int y){
int tx=x,ty=y;
vector<pair<int,int>>path;
while(1){
if(tx<1||tx>n||ty<1||ty>m) return ;
if(vis[tx][ty]){
int cur=path.end()-find(path.begin(),path.end(),make_pair(tx,ty));
for(auto it=find(path.begin(),path.end(),make_pair(tx,ty));it!=path.end();++it) v[it->first][it->second]=cur;
return ;
}
vis[tx][ty]=1;
path.push_back({tx,ty});
if(g[tx][ty]=='U') tx--;
else if(g[tx][ty]=='D') tx++;
else if(g[tx][ty]=='L') ty--;
else if(g[tx][ty]=='R') ty++;
}
}
int dfs(int x,int y){
if(x<1||x>n||y<1||y>m) return 0;
if(v[x][y]) return v[x][y];
if(g[x][y]=='U') return v[x][y]=dfs(x-1,y)+1;
else if(g[x][y]=='D') return v[x][y]=dfs(x+1,y)+1;
else if(g[x][y]=='L') return v[x][y]=dfs(x,y-1)+1;
else if(g[x][y]=='R') return v[x][y]=dfs(x,y+1)+1;
return v[x][y];
}
void solve(){
cin >> n >> m;
int resx,resy,ans=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin >> g[i][j]; v[i][j]=0; vis[i][j]=false;
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(!vis[i][j]) check(i,j);
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
dfs(i,j);
if(ans<v[i][j]) ans=v[i][j],resx=i,resy=j;
}
}
cout << resx << ' ' << resy << ' ' << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t; cin >> t;
while(t--){
solve();
}
return 0;
}
|
