大致思路:尝试依次更改每个镜子的方向 如果成立就输出此镜子的序号
最终代码99行 能AC就行(
此写法有些略显繁琐 仅供于参考思路
#include <bits/stdc++.h>
using namespace std;
const int N=210;
int n;
int mx, my;
vector<int> ax, ay;
void f(vector<int> &v)
{
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end())-v.begin());
}
struct Node
{
int x=0, y=0, id=-1;
void f()
{
x=lower_bound(ax.begin(), ax.end(), x)-ax.begin()+1;
y=lower_bound(ay.begin(), ay.end(), y)-ay.begin()+1;
}
void input(int i)
{
cin>>y>>x;
id=i;
}
}pt[N];
const int D[4][2]={{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int T[2][4]={{3, 2, 1, 0}, {1, 0, 3, 2}};
bool rt[N];
int tag[N][N];
bool st[N][N][4];
bool solve()
{
memset(st, 0, sizeof st);
bool flag=false;
int d=1;
int x=pt[n+1].x, y=pt[n+1].y;
while(1)
{
if(x==pt[0].x && y == pt[0].y)
{
flag=true;
break;
}
if(x<1 || x>mx || y<1 || y>my || st[x][y][d]) break;
st[x][y][d]=true;
if(tag[x][y]!=-1) d=T[tag[x][y]][d];
x+=D[d][0], y+=D[d][1];
}
return flag;
}
int main()
{
cin>>n;
pt[0].input(0);
for(int i=1; i<=n; i++)
{
pt[i].input(i);
char c; cin>>c;
rt[i]=(c=='/');
}
for(int i=0; i<=n+1; i++)
{
ax.push_back(pt[i].x);
ay.push_back(pt[i].y);
}
f(ax); f(ay);
mx=ax.size(), my=ay.size();
memset(tag, -1, sizeof tag);
for(int i=0; i<=n+1; i++)
{
pt[i].f();
if(i>=1 && i<=n)
tag[pt[i].x][pt[i].y] = rt[pt[i].id];
}
if(solve()) cout<<0;
else
{
int ans=-1;
for(int i=1; i<=n; i++)
{
tag[pt[i].x][pt[i].y]^=1;
if(solve())
{
ans=i;
break;
}
tag[pt[i].x][pt[i].y]^=1;
}
cout<<ans;
}
return 0;
}
是将每个镜子看做图中的每一点,然后连接起来,枚举每个镜子,然后然是否可以走到b吗
光是将镜子与镜子连接起来就够麻烦的了,
是的 这题麻烦的就是这点
不能枚举每个镜子吧,可以到达 (a,b)点的镜子方式太多了,如果一开始就超过了b那就可能一直顺时针旋转无限趋近于目标点
先根据一面镜子来找下一面镜子 如果陷入循环 或者 最终没有到达谷仓就翻转下一面镜子 这个思路没有问题啊
不会无限循环的
那镜子太多容易超时啊,那你这根据哪个镜子反射也得枚举一遍,效率太低了
毕竟模拟题 而且N<=200 这种思路肯定是能过的
才200个啊,枚举每一个是200,爆搜一遍也才200,再加上每次二分也就大概 200 * 200 * 8左右妥妥过啊