AcWing 1986. Mirror (simulation, ring diagram)

【 Title Description 】
Farmer John's cows caused too much trouble around the farm , So John wants to keep a closer eye on them .
By installing... At various locations on the farm $N$ A reflective fence , He hopes to learn from $(0,0)$ Location of the house to see $(a,b)$ Location of the cowshed .
In the two-dimensional plan of John's farm , enclosure $i$ Expressed in integer position coordinates $(x_i,y_i)$ Centered tilt $45$ degree （ Such as / or \） Short line segment of .
for example , With $(3,5)$ Centered , Form like / The fence can be described as from $(2.9,4.9)$ To $(3.1,5.1)$ The line segment .
Each fence （ And the location of the cowshed ） In different locations .
$(0,0)$ and $(a,b)$ There is no fence .
John plans to sit in his house $(0,0)$ It's about , And straight to the right （ Along the $+x$ Direction ） see .
When his eyes reflected from some reflective fences on the farm , He wants to see something $(a,b)$.
Unfortunately , He thought that one of the reflective fences was placed in the wrong direction , For example, it should be /, But it was \.
Please output... In the given reflective fence , The first one can make John succeed by changing his orientation $(a,b)$ The sequence number of the fence .
If John doesn't need to switch the orientation of any fence, he can already see the point $(a,b)$ The output $0$.
If John can't see the point by switching the orientation of a single fence $(a,b)$ The output $-1$.

【 Input format 】
The first line contains three integers $N,a,b$.
Next $N$ That's ok , Among them the first $i$ Line description page $i$ Location and orientation of fence No . First contain two integers $x_i,y_i$ Indicates the position of its center point , Then it contains a character / or \ Indicates that the fence faces .
Fence number from $1$ Start .

【 Output format 】
The first output can make John successfully see the point by changing its orientation $(a,b)$ The sequence number of the fence .
If John doesn't need to switch the orientation of any fence, he can already see the point $(a,b)$ The output $0$.
If John can't see the point by switching the orientation of a single fence $(a,b)$ The output $-1$.

【 Data range 】
$1\le N\le 200$
$-10^6\le x_i,y_i,a,b\le 10^6$

【 sample input 】

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

【 sample output 】

4

【 Sample explanation 】
The plan of the farm is as follows , among $H$ John's house means ,$B$ Indicates a cowshed ：

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

By changing $(3,2)$ The fence at the is facing , So John can see something $(a,b)$, As shown below ：

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

【 analysis 】

---

First, judge whether the initial graph can reach the end , If it can be reached, it will output $0$, Otherwise, enumerate which mirror to flip , After turning over, simulate again to judge whether you can reach the end , Output the mirror number if possible , Otherwise, turn the current mirror back , Continue to judge the next mirror .

How to simulate and judge whether you can go from the origin to the destination ？ Suppose the origin number is $0$, The end point number is $n+1$, The initial point $k=0$. When the number of points passed exceeds $(n+1)\ast 2$ It means that there is a ring , Can't get to the end . Otherwise enumerate each point , Judge whether this point is in the moving direction of the current point , Find the point closest to the current point in the moving direction , Then go to this point . If you can't find the point in the current moving direction after enumerating all the points, you will walk out of the boundary , Can't get to the end .

---

【 Code 】

#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 Indicates the current moving direction ,k Indicates the current point label ,0 Represents the origin 
    for (int i = 0; i < (n + 1) * 2; i++)// Go through all (n + 1) * 2 A point has not reached the end, indicating that there is a ring 
    {
    
        int id = -1, dis = 0x3f3f3f3f;//id Indicates the point label closest to the current point in the current moving direction ,dis Represents the distance 
        for (int j = 1; j <= n + 1; j++)
        {
    
            if (j == k) continue;// Skip the point itself 
            // Judge separately j Coordinates of (x, y) Is it at point k In the current direction of movement 
            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;// There is no mirror or end point in the current moving direction , That is out of bounds 
        else if (id == n + 1) return true;// You can reach the destination in the current moving direction 
        k = id;// Update the position of the current point 
        if (p[id].c == '/') d ^= 1;
        else d ^= 3;
    }
    return false;
}

int main()
{
    
    cin >> n >> p[n + 1].x >> p[n + 1].y;// The first n + 1 Points represent the end point 
    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;
}