Problem - 1607F - Codeforces

题目大意：

​ 有一个n*m的矩形地图，每个点有RLUD，表示在该点下一步走个方向，走出地图或者走到走过的点机器人就会损毁。问从哪个点开始走能走最长的路径。

思路：

​ 对于每一个点他之后的路径都是确定的，所以可以通过记忆化（设置dp数组）来降低时间复杂度。值得注意的是环的处理 。

​ 出现环时，需要把整个环里的每个节点设置成环的周长。因为不论从哪个点进入该环，他最多就只能沿着环走一圈。

​ 还有就是注意不能开ll。开ll就mle。卡了好久

代码：

#define show2(a , n , m) for(int i = 1 ; i <= n ; i ++ , cout << "\n")for(int j = 1 ; j <= m ; cout << a[i][j ++ ] << " " )
#define get2(a , n , m) for(int i = 1 ; i <= n ; i ++ )for(int j = 1 ; j <= m ; j ++ ) cin >> a[i][j] ;
#define show1(a , n) for(int i = 1 ; i <= n ; i ++ ) cout << a[i] << " "; cout << "\n" ;
#define get1(a , n) for(int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
#define pll pair< long long , long long >
#define pii pair< int , int >
#define debug cout<<"= =\n"
#include<bits/stdc++.h>
#define YES puts("YES")  
#define NO puts("NO")  
#define se second
#define fi first 
 
using namespace std ;
typedef int ll ;//<============================这里把ll定义成int了，后面所有ll都是int
const ll mod = 1e9 + 7 ;
const ll N = 2e3 + 5 ;
const ll INF = 0x3f3f3f3f ;

char s[N][N] ;
ll dp[N][N] ;
bool vis[N][N] ;
pll rec[N * N] ;
ll cnt , n , m ;

ll dfs(ll i , ll j){//cout << i << " " << j << "\n" ;
	rec[ ++ cnt ] = {i , j} ;//记录路径
	if(i > n || i < 1 || j > m || j < 1 || dp[i][j] || vis[i][j])return dp[i][j] ;
	vis[i][j] = 1 ;
	if(s[i][j] == 'D')return dp[i][j] = 1 + dfs(i + 1 , j) ;
	if(s[i][j] == 'U')return dp[i][j] = 1 + dfs(i - 1 , j) ;
	if(s[i][j] == 'R')return dp[i][j] = 1 + dfs(i , j + 1) ;
	if(s[i][j] == 'L')return dp[i][j] = 1 + dfs(i , j - 1) ;
	
}

void solve(){
	ll ans = 0 , I , J ;
	cin >> n >> m ;
	get2(s , n , m) ;
	for(int i = 1 ; i <= n + 1 ; i ++ )
	for(int j = 1 ; j <= m + 1 ; j ++ ) dp[i][j] = vis[i][j] = 0 ;
	
	for(int i = 1 ; i <= n ; i ++ )
	for(int j = 1 ; j <= m ; j ++ ){
		cnt = 0 ;
		ll tmp = dfs(i , j) ;
		if(tmp > ans){
			ans = tmp ; I = i , J = j ;
		}
		pll t = rec[cnt] ;//判判断该路径中有没有出现环
		for(int k = 1 ; k < cnt ; k ++ ){
			if(rec[k] == t){//出现环（首尾相同） 
				ll len = k ;
				while(k <= cnt) dp[rec[k].fi][rec[k].se] = cnt - len , k ++ ;
			}//cnt - len是环周长
		}
	}
	
	cout << I << " " << J << " " << ans << "\n" ;
}

int main(){
	ios::sync_with_stdio(false) ;
	cin.tie(0) ; cout.tie(0) ;
	
	ll T ; cin >> T ;
	while(T -- ) solve() ;
	
}