题目描述
样例
blablabla
(模拟) $O(n^2)$
从下午3点写到了晚上9点,感谢个位大佬提供的思路
以下是个人理解的大体的思路
第一次看完题目之后,之前做过一个镜子的题目,关于光照在玻璃上的反射其实有如下情况
如图:
由于该题想要找到第一个通过该镜子折射就能到达(a,b)的围栏,因此,明确所有的各个方向从哪经过哪种镜子走到哪很有必要
如图:
终点是(a,b)且经过折射能够看到(a,b)我们假设光射入的方向为d,对于无论是折射进入的光线还是折射进去的光线,如果满足了条件就已经找到了
故需要编写check函数,
(1).从初始位置直接射入就能满足要求
t还有一种可能就是
`
1 100 0
1 0 /
此时肯定照不过去,需要做出特判
(2).从各个方向射入依照初始分析的方位表来进行编写判断
注意:由于可能会经过光的折射之后会出现重环的情况,如下:
这样需要引入一个st数组用来记录每个镜子的走过次数,如果大于等于2次,则直接跳出
关于dfs函数的编写:
我们的需求上是想要找到第一个能够满足条件的点换句话来说,也就是想要找到最先路径能够满足条件的点,能够解决这种问题的做法为:
在所有镜子中,找到x方向/y方向中选择相邻镜子或者镜子到(a,b)点最短的距离,这样一定会最快也一定是第一个能够找到的
算法1
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 220,INF=0x3f3f3f3f;
typedef pair<int, int> PII;
int st[N];//存储某个镜子的经过次数
char g[N];//存储镜子的状态
PII p[N];//存储镜子的中心点的坐标
int n,a,b;
int res=INF;//表示该镜子的位置
//用于判断是否这个镜子经过反射是否能够看到(a,b),d为从该镜子射出去的线将要走的方向
bool check(int x,int y,int d)
{
//特判1种样例
/*
1 100 0
1 0 /这种情况是一定输出为-1的
*/
if(d==1&&x==0&&y==0)
for(int i=1;i<=n;i++)
if(p[i].first>x&&p[i].second==y)return false;
return((d==0&&x==a&&y<b)||(d==1&&x<a&&y==b)||(d==2&&x==a&&y>b)||(d==3&&x>a&&y==b));
}
bool dfs(int x,int y,int d,int u)
{
if(check(x,y,d))//说明折射之后能够看到(a,b)
{
res=u;
return true;
}
int minn=INF,idx=0;//寻找最小路径,idx用来存一下当前光线所到达的某个镜子的序号
for(int i=1;i<=n;i++)
{
if(st[i]>=2)continue;//可能出现重环,因此出现两次的需要用st做下判断
/*
20 17 -17
5 0 /
5 5 \
0 5 \
0 -5 \
5 -5 /
10 0 \
10 -10 \
11 -10 \
11 -11 \
12 -11 \
12 -12 \
13 -12 \
13 -13 \
14 -13 \
14 -14 \
15 -14 \
15 -15 \
16 -15 \
16 -16 \
17 -16 \
*/
//通过样例发现,在直线方向寻找最短的那条路径折射,一定镜子会有机会最先到达路径点
int x1=p[i].first,y1=p[i].second;
//x方向
if((d==1&&x1>x&&y1==y)||(d==3&&x1<x&&y1==y))
{
if(minn>abs(x-x1))minn=abs(x-x1),idx=i;//更新当前走到的第几位镜子
}
//更新y方向
else if((d==2&&x1==x&&y1<y)||(d==0&&x1==x&&y1>y))
{
if(minn>abs(y-y1))minn=abs(y-y1),idx=i;
}
else continue;//没有则直接跳过
}
if(minn!=INF)
{
st[idx]++;//说明当前编号的镜子走过
if(g[idx]=='/')d^=1;
else d^=3;
return dfs(p[idx].first,p[idx].second,d,u);//递归查找
}
else return false;
}
int main()
{
scanf("%d%d%d", &n,&a,&b);
for(int i=1;i<=n;i++)
{
int l,r;
char m;
cin>>l>>r>>m;
p[i]={l,r};
g[i]=m;
}
bool flag=dfs(0,0,1,0);
/*if(dfs(0,0,1,0))//1是初始第一次走的方向,先初始走一次,0是第一次不需要修改所以编号为0
{
cout<<0<<endl;
return 0;
}*/
//不断改变一个镜子的位置在枚举一次
for(int i=1;i<=n &&!flag;i++)
{
memset(st, 0, sizeof st);//每遍历一次需要清空
// int x=p[i].x,y=p[i].y;
if(g[i]=='/')g[i]='\\';
else g[i]='/';//改变镜子走向
flag=dfs(0,0,1,i);
if(g[i]=='/')g[i]='\\';//一个反斜杠是多转义字符的开始,没有\\之说
else g[i]='/';//还原更改的镜子
}
if(res==INF)cout<<-1<<endl;
else cout<<res<<endl;
return 0;
}