AcWing 1986. 镜子(模拟中的几个注意点)
原题链接
简单
作者:
生在逢时
,
2022-04-28 08:27:35
,
所有人可见
,
阅读 227
130行代码模拟过
期间用const_cast 来解除 set 迭代器的底层 const
几个注意点
1、(0, 0)点可能经过多次(当第二次经过时不用管他,直接顺延)
2、可能会进入死循环(要特判)
3、农夫约翰只向右看(没看到,卡了我半天)
仅提供注意点,代码繁琐仅供参考(有大佬来优化当然是更好啦)
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#define ft first
#define sd second
using namespace std;
int m, a, b;
map<int, set<int>> colmp;//维护每行对应的镜子纵坐标
map<int, set<int>> rowmp;//维护每列对应的镜子横坐标
map<pair<int, int>, pair<int, char>> mir;//维护每个镜子的坐标及序列和镜子的状态
//右:0,左:1,上:2,下:3
//"/":x^3 , "\":x^2
void init()//初始化把棚屋和围栏插进去
{
colmp[0].insert(0);
rowmp[0].insert(0);
colmp[a].insert(b);
rowmp[b].insert(a);
}
bool search(int n)
{
int x = 0, y = 0;
int cnt = 0;
bool st = false;//标定是否第一次经过(0,0)点
while(1)
{
cnt ++;
if (cnt == m + 3) return false;//可能进入死循环,当循环达到一定程度,跳出返回false即可
if (!n || n == 1)//从左或右进
{
auto &u = rowmp[y];//找到该列对应的横坐标
auto idx = u.find(x);//找到该点相应的位置
if (n == 1)//从左进
{
if (++idx == u.end()) return false;//如果点右侧没有镜子了,查找结束返回false
x = const_cast<int&>(*idx);// const_cast 来解除 set 迭代器的底层 const(如果改变该数值,就会破坏了 s 的有序性)
if (x == 0 && y == 0 && st)//如果不是第一次经过(0, 0),要方向不变的跳过(0,0)
{
if (++idx == u.end()) return false;//向上同理
x = const_cast<int&>(*idx);
}
if (x == a && y == b) return true;//如果是(a, b)围栏点,返回true
if (mir[{x, y}].sd == '/') n ^= 3; else n ^= 2;//通过镜子改变方向
}
else//从右进
{
if (idx == u.begin()) return false; idx--;
x = const_cast<int&>(*idx);
if (x == 0 && y == 0 && st)
{
if (idx == u.begin()) return false; idx--;
x = const_cast<int&>(*idx);
}
if (x == a && y == b) return true;
if (mir[{x, y}].sd == '/') n ^= 3; else n ^= 2;
}
}
else//从上或下进
{
auto &u = colmp[x];
auto idx = u.find(y);
if (n == 2)
{
if (++idx == u.end()) return false;
y = const_cast<int&>(*idx);
if (x == 0 && y == 0 && st)
{
if (++idx == u.end()) return false;
y = const_cast<int&>(*idx);
}
if (x == a && y == b) return true;
if (mir[{x, y}].sd == '/') n ^= 3; else n ^= 2;
}
else
{
if (idx == u.begin()) return false; idx--;
y = const_cast<int&>(*idx);
if (x == 0 && y == 0 && st)
{
if (idx == u.begin()) return false; idx--;
y = const_cast<int&>(*idx);
}
if (x == a && y == b) return true;
if (mir[{x, y}].sd == '/') n ^= 3; else n ^= 2;
}
}
st = true;//经过一次后,直接标定,下次不用了
}
}
int main()
{
cin >> m >> a >> b;
init();//初始化把棚屋和围栏插进去
for (int i = 1; i <= m; i ++ )
{
int x, y; char c;
cin >> x >> y >> c;
auto &u = colmp[x];
u.insert(y);//将每行对应的纵坐标存储
auto &v = rowmp[y];
v.insert(x);//将每列对应的横坐标存储
mir[{x, y}] = {i, c};
}
bool st = false;
st = search(1); if (st) {cout << '0' << endl; return 0;} //没有改变镜子
int res = m;
for (auto &t : mir)//改变每一个镜子
{
bool stt;
//改变镜子
int u = t.sd.sd;
if (u == '/') t.sd.sd = '\\';
else t.sd.sd = '/';
stt = search(1);
if (stt) {res = min(res, t.sd.ft); st = true;}//找到改变镜子编号最小(第一个镜子)且能看到围栏的镜子
t.sd.sd = u;//恢复镜子
}
if (!st)
cout << "-1" << endl;
else cout << res << endl;
return 0;
}