AcWing 1986. 镜子（模拟，环图）

【题目描述】
农夫约翰的奶牛在农场周围造成了太多麻烦，因此约翰希望对它们保持更密切的关注。
通过在农场的各个位置安装$N$个反光围栏，他希望能够从$(0,0)$位置的房子看到$(a,b)$位置的牛棚。
在约翰农场的二维平面图中，围栏$i$表示为以整数位置坐标$(x_i,y_i)$为中心的倾斜$45$度（如/或\）的短线段。
例如，以$(3,5)$为中心，形如/的围栏可以描述为从$(2.9,4.9)$到$(3.1,5.1)$的线段。
每个围栏（以及牛棚的位置）位于不同的位置。
$(0,0)$和$(a,b)$处无围栏。
约翰计划坐在他的房屋$(0,0)$处，并直接向右（沿$+x$方向）看。
当他的目光从农场的一些反光围栏上反射出来时，他希望能够看到点$(a,b)$。
不幸的是，他认为其中一个反光围栏的摆放朝向不对，例如应该为/，却摆成了\。
请输出给定反光围栏中，第一个能够通过改变其朝向使得约翰成功看到点$(a,b)$的围栏的顺序编号。
如果约翰不需要切换任何围栏的朝向就已经可以看到点$(a,b)$则输出$0$。
如果约翰无法通过切换单个围栏的朝向使自己看到点$(a,b)$则输出$-1$。

【输入格式】
第一行包含三个整数$N,a,b$。
接下来$N$行，其中第$i$行描述第$i$号围栏的位置和朝向。首先包含两个整数$x_i,y_i$表示其中心点位置，然后包含一个字符/或\表示围栏朝向。
围栏编号从$1$开始。

【输出格式】
输出第一个能够通过改变其朝向使得约翰成功看到点$(a,b)$的围栏的顺序编号。
如果约翰不需要切换任何围栏的朝向就已经可以看到点$(a,b)$则输出$0$。
如果约翰无法通过切换单个围栏的朝向使自己看到点$(a,b)$则输出$-1$。

【数据范围】
$1\le N\le 200$
$-10^6\le x_i,y_i,a,b\le 10^6$

【输入样例】

5 6 2
3 0 /
0 2 /
1 2 /
3 2 \
1 3 \

【输出样例】

4

【样例解释】
农场的平面图如下所示，其中$H$表示约翰的房子，$B$表示牛棚：

3 .\.....
2 //.\..B
1 .......
0 H../...
  0123456

通过改变$(3,2)$处的围栏朝向，就可以使约翰看到点$(a,b)$，如下所示：

3 .\.....
2 //./--B
1 ...|...
0 H--/...
  0123456

【分析】

---

首先对初始的图先判断是否能够走到终点，如果能走到则输出$0$，否则就枚举翻转哪一个镜子，翻转后模拟一遍判断是否能够走到终点，如果可以则输出镜子编号，否则将当前镜子翻转回去，继续判断下一个镜子。

如何模拟判断从原点是否能够走到终点呢？假设原点编号为$0$，终点编号为$n+1$，初始所在的点$k=0$。当所经过的点数超过$(n+1)\ast 2$时说明有环，无法走到终点。否则枚举每个点，判断这个点是否在当前点的移动方向上，找出在该移动方向上距离当前点最近的点，然后走到这个点上。如果枚举完所有点都没找到当前移动方向上的点说明往前走将会走出界，无法走到终点。

---

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 210;
int n;
int dx[4] = {
     0, 1, 0, -1 }, dy[4] = {
     1, 0, -1, 0 };

struct Point
{
    
    int x, y;
    char c;
}p[N];

void rotate(char &c)
{
    
    if (c == '/') c = '\\';
    else c = '/';
}

bool check()
{
    
    int d = 1, k = 0;//d表示当前移动方向，k表示当前所在的点标号，0表示原点
    for (int i = 0; i < (n + 1) * 2; i++)//遍历完所有(n + 1) * 2个点还没到终点说明有环
    {
    
        int id = -1, dis = 0x3f3f3f3f;//id表示在当前移动方向上离当前点最近的点标号，dis表示距离
        for (int j = 1; j <= n + 1; j++)
        {
    
            if (j == k) continue;//跳过这个点本身
            //分别判断点j的坐标(x, y)是否在点k的当前移动方向上
            if (p[k].x + abs(p[k].x - p[j].x) * dx[d] != p[j].x) continue;
            if (p[k].y + abs(p[k].y - p[j].y) * dy[d] != p[j].y) continue;
            int t = abs(p[k].x - p[j].x) + abs(p[k].y - p[j].y);
            if (t < dis) dis = t, id = j;
        }
        if (id == -1) return false;//当前移动方向上没有镜子和终点，即走出界了
        else if (id == n + 1) return true;//当前移动方向上能走到终点
        k = id;//更新当前点的位置
        if (p[id].c == '/') d ^= 1;
        else d ^= 3;
    }
    return false;
}

int main()
{
    
    cin >> n >> p[n + 1].x >> p[n + 1].y;//第n + 1个点表示终点
    for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y >> p[i].c;
    if (check()) cout << 0 << endl;
    else
    {
    
        for (int i = 1; i <= n; i++)
        {
    
            rotate(p[i].c);
            if (check()) {
     cout << i << endl; return 0; }
            rotate(p[i].c);
        }
        cout << -1 << endl;
    }
    return 0;
}