C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 1e6+100;
int row[N], col[N];
char ops[N];
int n, a, b, maxx, maxy, minx = INT_MAX, miny = INT_MAX;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
map<int, vector<int>> xx, yy;
map<pair<int, int>, char> st;
set<pair<pair<int, int>, int>> visited;
// 求下一个镜子位置的辅助函数
int get(int a, int b, map<int, vector<int>> &aa, int mark) {
// 用xx,yy缓存每行x中y的坐标值和每列y中x的坐标值,就可以在dfs搜索时根据方向找到下一个镜子所在的点
if (!aa.count(a)) return INF;
auto nxt = aa[a];
sort(nxt.begin(), nxt.end());
if (mark) {
reverse(nxt.begin(), nxt.end());
}
for (auto ii : nxt) {
if (mark) {
if (ii < b) return ii;
} else {
if (ii > b) return ii;
}
}
return INF;
}
bool dfs(int x, int y, int d) {
if (visited.count({{x, y}, d})) return false; //用visited来防止光线陷入环中
if (st.count({x, y})) visited.insert({{x, y}, d});
if (x == a && y == b) return true;
int nx = INF, ny = INF;
// 下面是根据方向找下一个镜子的位置,此处枚举了每个方向,没有想到怎么优化代码
if (d == 0) nx = x, ny = get(x, y, xx, 0);
else if (d == 1) nx = get(y, x, yy, 0), ny = y;
else if (d == 2) nx = x, ny = get(x, y, xx, 1);
else nx = get(y, x, yy, 1), ny = y;
if (nx == INF || ny == INF) return false;
if (st.count({nx, ny})) {
if (st[{nx, ny}] == '/') d ^= 1;
else d = 3 - d;
}
return dfs(nx, ny, d);
}
//辅助函数,用来check不做修改和修改位置i时是否能看到牛棚
bool check(int x, int y, int i) {
if (i >= 0) {
if (ops[i] == '/') ops[i] = '\\';
else ops[i] = '/';
st[{row[i], col[i]}] = ops[i];
}
visited.clear();
bool res = dfs(0, 0, 1);
if (i >= 0) {
if (ops[i] == '/') ops[i] = '\\';
else ops[i] = '/';
st[{row[i], col[i]}] = ops[i];
}
return res;
}
//辅助函数:处理get函数中用到的xx和yy缓存,并保存一个全局最大和最小值用于终止dfs搜索
void process(int a, int b) {
maxx = max(maxx, a), maxy = max(maxy, b);
minx = min(minx, a), miny = min(miny, b);
xx[a].push_back(b), yy[b].push_back(a);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a >> b;
process(a, b);
for (int i = 0; i < n; i++) {
cin >> row[i] >> col[i] >> ops[i];
process(row[i], col[i]);
st[{row[i], col[i]}] = ops[i];
}
bool flag = false;
for (int i = -1; i < n; i++) {
if (check(0, 0, i)) {
cout << i + 1 << endl;
flag = true;
break;
}
}
if (!flag) cout << -1 << endl;
return 0;
}