题目链接：http://codeforces.com/problemset/problem/89/C
The first line contains two integers n and m (1?≤?n,?m,?n?×?m?≤?5000). Then follow n lines containing m characters each — that is the game field description. "." means that this square is empty. "L", "R", "U", "D" mean that this square contains a chip and an arrow on it says left, right, up or down correspondingly.
It is guaranteed that a field has at least one chip.
Print two numbers — the maximal number of points a player can get after a move and the number of moves that allow receiving this maximum number of points.
4 4 DRLD U.UL .UUR RDDL
10 1
3 5 .D... RRRLL .U...
6 2
In the first sample the maximum number of points is earned by the chip in the position (3,?3). You can see its progress at the following picture:
All other chips earn fewer points.
题意：给出n*m的矩阵，其中有的方格内是箭头（上、下、左、右四种），可以从一个箭头走到它所指方向最近的箭头（一个箭头只可以到一次），对于一个点(x,y)开始的答案是从(x,y)按箭头方向一直走下去所经过的箭头数量，求从某点开始的最大答案。
解析：直接dfs会超时，这里用十字链表存储每个箭头上下左右最近的箭头位置，基于此来dfs就可以
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 5005;char maze[M][M];
int n,m;
//L[i]是位于i处的箭头左边第一个箭头的位置
//R[i]是位于i处的箭头右边第一个箭头的位置
//U[i]是位于i处的箭头上边第一个箭头的位置
//D[i]是位于i处的箭头下边第一个箭头的位置
int U[M],D[M],L[M],R[M];void getUDLR()//初始化完成之后，每个箭头存储了上下左右最近的箭头位置
{for(int i=0;i<n;i++){int l=-1;for(int j=0;j<m;j++){if(maze[i][j]!='.'){int index=i*m+j;L[index]=l;if(l!=-1) R[l]=index;l=index;}}R[l]=-1;}for(int j=0;j<m;j++){int u=-1;for(int i=0;i<n;i++){if(maze[i][j]!='.'){int index=i*m+j;U[index]=u;if(u!=-1) D[u]=index;u=index;}}D[u]=-1;}
}void Delete(int x,int y)
{int index=x*m+y;//index上面的箭头为U[index],删除index之后,“U[index]下面的箭头”不再是“index”而是“index下面的箭头D[index]”if(U[index]!=-1) D[U[index]]=D[index];if(D[index]!=-1) U[D[index]]=U[index];if(L[index]!=-1) R[L[index]]=R[index];if(R[index]!=-1) L[R[index]]=L[index];
}int dfs(int x,int y)
{Delete(x,y);//本次dfs中将用过的箭头删除int index=x*m+y;switch(maze[x][y]){case 'U':if(U[index]==-1) return 1;else return 1+dfs(U[index]/m,y);break;case 'D':if(D[index]==-1) return 1;else return 1+dfs(D[index]/m,y);break;case 'L':if(L[index]==-1) return 1;else return 1+dfs(x,L[index]%m);break;case 'R':if(R[index]==-1) return 1;else return 1+dfs(x,R[index]%m);break;}
}int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%s",maze[i]);int maxV=-1,num=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(maze[i][j]!='.'){getUDLR();int res=dfs(i,j);if(res>maxV) { maxV=res; num=1;}else if(res==maxV){ num++;}}}}printf("%d %d\n",maxV,num);return 0;
}
参考：https://www.cnblogs.com/debugcool/archive/2011/06/21/CF74.html