感觉好像要用到遍历,范围是1000
若可以无限反射,可知前提是内部可以形成一个环,话句话就是外部是进不来的
所以这样的光线是进不去这个环的,所以是不可能有无线反射的情况的
所以最多也就走10001000个点,这完全可以进行遍历,但是从哪个入口进去
但是一共有2000个入口,这样就不能遍历了
但是我们想一下,若一个点连续被走了两次,我们向前或者向后继续推,
我们可以发现路径唯一推出两个入口,这样10001000个点只可能被遍历两边
且这两边的入口与出口是对应的(这个入口是另一个的出口,这个出口是另一个的入口)
但是我们并不能求出哪俩个是对应的,所以还是要一一遍历
所以我们实际遍历的点为1000*1000,虽然入口那么多,但是实际遍历还是那么多
这里我们需要考虑一下实际的转换问题
“/”上转换左,左转换上,右转换下,下转换右
“\”上转换右,右转换上,下转换左,左转换下
我们将上下左右转为 1 2 3 4
“/”变为4 3 2 1(我们直接用5减)
“\”变为3 4 1 2(我们发现可以加2再%4)
这样就能都算出来啦,代码如下
#include<iostream>
using namespace std;
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};// 1 2 3 4 上下左右
int res,n,m;
char g[1010][1010];
void dfs(int a,int b,int fx,int u)
{
res=max(res,u);
if(g[a][b]=='\\')
{
fx=(fx+2)%4;
if(!fx)fx=4;
}
else
{
fx=5-fx;
}
int x=a+dx[fx],y=b+dy[fx];
if(x>=1&&x<=n&&y>=1&&y<=m)dfs(x,y,fx,u+1);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
//枚举入口
for(int i=1;i<=n;i++)
{
dfs(i,1,4,1);//向右
dfs(i,m,3,1);//向左
}
for(int i=1;i<=m;i++)
{
dfs(1,i,2,1);//向下
dfs(n,i,1,1);//向上
}
cout<<res;
}