传送门

题意：

n×m的网格上，有k个镜子，光线反射规则如下：

现在给出初始光线的位置以及光线的射出方向，求光线能经过多少个格子的中心

光线走到边缘也会被反射

n,m,k<=1e5

Solution:

暴力模拟即可，但是大家可能会想到一点：光线可能会经过重复的砖块的中心，但是仔细思考一下就会发现这种情况是不可能发生的，因为每次如果不是原路返回的反射的话光线的坐标x+y的奇偶性就会改变

这样一来就简单了，我们开n+m-1个vector记录每一条主对角线和副对角线上的镜子的位置，然后每次射出光线时在对应的对角线上二分查找即可

注意如果出现原路返回的反射的话需要从原位置反方向再搞一遍

写的时候还发现如果初始位置处于一条光路的中间位置的话统计答案会很难办，所以我们可以先让光线射一次，然后再执行我们的算法

细节比较多的一道题，可以用来练习代码能力

代码（可能写的比较丑QWQ）：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map> 
#include<vector>
#define mp(a,b) make_pair(a,b)
using namespace std;
const int N=100010;
int n,m,k,x,y;
char s[5];
struct mirror{
    int x,y;
}q[N];
vector<int>zhu[2*N],fu[2*N];
map<pair<int,int>,bool>vis;
map<pair<int,int>,bool>p;
int id;
int dx,dy;
long long ans,tot; 
int find(bool x,int i,int l,int r,int pos)
{
    int as=-1;
    if (x==1)
    {
        while (l<=r)
        {
            int mid=l+r>>1;
            if (zhu[i][mid]<pos) as=zhu[i][mid],l=mid+1;//SW
            else r=mid-1;
        }
        return as;
    }
    else
    {
        while (l<=r)
        {
            int mid=l+r>>1;
            if (fu[i][mid]<pos) as=fu[i][mid],l=mid+1;//NW
            else r=mid-1;
        }
        return as;
    }
}
int findbig(bool x,int i,int l,int r,int pos)
{
    int as=-1;
    if (x==1)
    {
        while (l<=r)
        {
            int mid=l+r>>1;
            if (zhu[i][mid]>pos) as=zhu[i][mid],r=mid-1;//SW
            else l=mid+1;
        }
        return as;
    }
    else
    {
        while (l<=r)
        {
            int mid=l+r>>1;
            if (fu[i][mid]>pos) as=fu[i][mid],r=mid-1;//NW
            else l=mid+1;
        }
        return as;
    }
}
bool run(int dx,int dy,int x,int y)
{
    tot=0;
    while (!p[mp(x,y)])
    {
        p[mp(x,y)]=1;
        if (dx+dy==0)
        {
            if (dx==1)//SW
            {
                int pos=find(1,x+y-1,0,zhu[x+y-1].size()-1,y);//zhu
                tot+=y-pos;
                x=x+y-1-pos;y=pos+1;
                if (vis[mp(x+1,y)]&&vis[mp(x,y-1)]) return 0;
                else if (vis[mp(x+1,y)]) dx=-dx,y--;
                else if (vis[mp(x,y-1)]) dy=-dy,x++;
                else return 0;
            }
            else//NE
            {
                int pos=findbig(1,x+y-1,0,zhu[x+y-1].size()-1,y);//zhu
                tot+=pos-y;
                x=x+y-1-pos+2;y=pos-1;
                if (vis[mp(x-1,y)]&&vis[mp(x,y+1)]) return 0;
                else if (vis[mp(x-1,y)]) dx=-dx,y++;
                else if (vis[mp(x,y+1)]) dy=-dy,x--;
                else return 0;
            }
        }
        else
        {
            if (dx==-1)///NW
            {
                int pos=find(0,m-y+x,0,fu[x+m-y].size()-1,y);
                tot+=y-pos;
                x=x-y+pos+1;y=pos+1;
                if (vis[mp(x-1,y)]&&vis[mp(x,y-1)]) return 0;
                else if (vis[mp(x-1,y)]) dx=-dx,y--;
                else if (vis[mp(x,y-1)]) dy=-dy,x--;
                else return 0;
            }
            else//SE
            {
                int pos=findbig(0,m-y+x,0,fu[x+m-y].size()-1,y);//zhu
                tot+=pos-y;
                x=x-y+pos-1;y=pos-1;
                if (vis[mp(x+1,y)]&&vis[mp(x,y+1)]) return 0;
                else if (vis[mp(x+1,y)]) dx=-dx,y++;
                else if (vis[mp(x,y+1)]) dy=-dy,x++;
                else return 0;
            }
        }
    }
    return 1;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=k;i++)
    {
        scanf("%d%d",&q[i].x,&q[i].y);
        vis[mp(q[i].x,q[i].y)]=1;
        zhu[q[i].x+q[i].y-1].push_back(q[i].y);
        fu[m-q[i].y+q[i].x].push_back(q[i].y);
    }
    for (int i=0;i<=n;i++)
    {
        vis[mp(i,0)]=1;
        zhu[i+0-1].push_back(0);
        fu[m-0+i].push_back(0);
    }
    for (int i=n+1;i>0;i--)
    {
        vis[mp(i,m+1)]=1;
        zhu[i+m+1-1].push_back(m+1);
        fu[m-(m+1)+i].push_back(m+1);
    }
    for (int i=0;i<=m;i++)
    {
        vis[mp(n+1,i)]=1;
        zhu[n+1+i-1].push_back(i);
        fu[m-i+n+1].push_back(i);
    }
    for (int i=m+1;i>0;i--)
    {
        vis[mp(0,i)]=1;
        zhu[0+i-1].push_back(i);
        fu[m-i+0].push_back(i);
    }
    for (int i=1;i<=n+m-1;i++) sort(zhu[i].begin(),zhu[i].end()),sort(fu[i].begin(),fu[i].end()); 
    scanf("%d%d%s",&x,&y,s);
    if (s[0]=='N'&&s[1]=='E') dx=-1,dy=1;
    else if (s[0]=='N'&&s[1]=='W') dx=-1,dy=-1;
    else if (s[0]=='S'&&s[1]=='W') dx=1,dy=-1;
    else if (s[0]=='S'&&s[1]=='E') dx=1,dy=1;
    if (dx+dy==0)
    {
        if (dx==1)//SW
        {
            int pos=find(1,x+y-1,0,zhu[x+y-1].size()-1,y);//zhu
            x=x+y-1-pos;y=pos+1;
            if (vis[mp(x+1,y)]&&vis[mp(x,y-1)]) dx=-dx,dy=-dy;
            else if (vis[mp(x+1,y)]) dx=-dx,y--;
            else if (vis[mp(x,y-1)]) dy=-dy,x++;
            else dx=-dx,dy=-dy;
        }
        else//NE
        {
            int pos=findbig(1,x+y-1,0,zhu[x+y-1].size()-1,y);//zhu
            x=x+y-1-pos+2;y=pos-1;
            if (vis[mp(x-1,y)]&&vis[mp(x,y+1)]) dx=-dx,dy=-dy;
            else if (vis[mp(x-1,y)]) dx=-dx,y++;
            else if (vis[mp(x,y+1)]) dy=-dy,x--;
            else dx=-dx,dy=-dy;
        }
    }
    else
    {
        if (dx==-1)///NW
        {
            int pos=find(0,m-y+x,0,fu[x+m-y].size()-1,y);
            x=x-y+pos+1;y=pos+1;
            if (vis[mp(x-1,y)]&&vis[mp(x,y-1)]) dx=-dx,dy=-dy;
            else if (vis[mp(x-1,y)]) dx=-dx,y--;
            else if (vis[mp(x,y-1)]) dy=-dy,x--;
            else dx=-dx,dy=-dy;
        }
        else//SE
        {
            int pos=findbig(0,m-y+x,0,fu[x+m-y].size()-1,y);//zhu
            x=x-y+pos-1;y=pos-1;
            if (vis[mp(x+1,y)]&&vis[mp(x,y+1)]) dx=-dx,dy=-dy;
            else if (vis[mp(x+1,y)]) dx=-dx,y++;
            else if (vis[mp(x,y+1)]) dy=-dy,x++;
            else dx=-dx,dy=-dy;
        }
    }
    if (run(dx,dy,x,y)) printf("%lld",tot);
    else
    {
        ans=tot-1;
        p[mp(x,y)]=0;
        dx=-dx,dy=-dy;
        run(dx,dy,x,y);
        ans+=tot;
        printf("%lld",ans);
    }
}