题目描述
给定若干镜子和目标点,观察点固定为$(0,0)$,初始方向为向右看
镜子的方向为/
或者\
如果每次只能改变一个镜子的方向,问能否观察到目标点
样例
本题中可能会出现循环光路
比如测试用例
4 4 -2
2 0 /
2 2 \
-2 2 /
-2 0 \
/...\..
.......
\.../..
算法1
(暴力枚举) $O(n^2)$
由于镜子总数只有200
个,每次改变一扇镜子,改变方向后,用dfs
看是否能到达目标点
方向只有4
个,可以用0~3
四个数来表示👇,👈,👆和👉,改变方向可以用异或运算,比如遇到\
,3
和0
相互转换通过和3
异或实现
3 ^ 3 = 3 1 ^ 3 = 2
0 ^ 3 = 0 2 ^ 3 = 1
时间复杂度
$O(n^2)$
C++ 代码
/*
方向 0, 1, 2, 3分别表示
👇, 👈, 👆, 👉
向下 向左 向上 向右
那么,方向的改变可以用异或来表示,比如
最开始为向右用3表示👉 ,遇到 / ,3^1=11^01=10=2,变为向上👆
*/
#include <iostream>
#include <set>
#include <map>
#include <vector>
#define x first
#define y second
using namespace std;
int n,ta,tb;//target_a,target_b,目标的横纵坐标
typedef pair<int, int> PII;
map<PII,char> idx;//存储每个镜子的方向
vector<PII> op;//存储输入镜子的序号
map<int,set<int>> a,b;//分别存储坐标为x和坐标为y的镜子坐标
int findxy(int dir, int cur, int xy, map<int,set<int>>& tmp){//寻找下一个位置的函数
if(dir==0||dir==1){
for(auto it = tmp[xy].rbegin(); it!=tmp[xy].rend(); it++){
if(*it<cur) return *it;
}
}
else{
for(auto it = tmp[xy].begin(); it!=tmp[xy].end(); it++){
if(*it>cur) return *it;
}
}
return 1e8;
}
int dfs()
{
int posa = 0, posb = 0, dir = 3;
map<PII,int> passed;
while(1){
if(dir==3||dir==1){//1, 3分别表示向左和向右,即光线沿水平方向传播
posa = findxy(dir, posa, posb, b);
}
else {//2, 0分别表示向上和向下,即光线沿垂直方向传播
posb = findxy(dir,posb, posa, a);
}
if(posa==ta&&posb==tb) return 1;
PII loc = {posa,posb};//下一个位置的坐标
if(idx.count(loc)==0) break;
if(idx[loc]=='/') dir^=1;//改变方向
else dir^=3;
if(posb==tb){
if(dir==1&&ta<=posa||dir==3&&ta>=posa) return 1;
}
if(posa==ta){
if(dir==2&&tb>=posb||dir==0&&tb<=posb) return 1;
}
if(posa==1e8||posb==1e8||passed.count(loc)&&passed[loc]==dir){//光路出界或者形成循环则跳出
break;
}
passed[loc]=dir;
}
return -1;
}
int main()
{
cin >> n >> ta >> tb;
//直接将目标点放入,便于处理
idx[{ta,tb}]='/';
a[ta].insert(tb);
b[tb].insert(ta);
for (int i = 0; i < n; i ++ ){
int x,y;
char t;
cin >> x >> y >> t;
idx[{x,y}] = t;
op.push_back({x,y});
a[x].insert(y);
b[y].insert(x);
}
int ans = -1;
if(dfs()!=-1){
cout << 0;
return 0;
};
for(int i = 0; i < n; i++){
char tmp=idx[op[i]];
if(idx[op[i]]=='/') idx[op[i]]='\\';
else idx[op[i]]='/';
if(dfs()!=-1){
ans = i+1;
break;
}
idx[op[i]] = tmp;
}
cout << ans;
return 0;
}