I题

首先容易知道一共只有4×n×m种状态，定义in[i][j][k]：以k方向射入(i,j)后被不同镜子反射的次数

（将上，下，左，右映射为 0，1，2，3 ）

（询问只可能是这些状态，所以先处理出所有的in[i][j][k]即可实现O(1)查询）

离线处理光链

光链的一定从迷宫外射入且一定会射出迷宫，处理迷宫四周射入的光链即可
搜索每条光链，然后存下路径及其信息
逆向遍历路径，遇到的镜子是第一次反射就cnt加1，遍历过程中给每个状态点赋为cnt（逆向遍历很好的解决了不同种类镜子反射的问题）（用哈希判断镜子是否是第一次反射）

处理光环

遍历所有4×n×m的状态点，还没有答案的状态点一定是在环中，所以搜索其所在的环
搜索环，dfn序判环，返回的时候给每个状态点赋为相同的答案

注意事项

相同的镜子反射多次只贡献1的答案
"|"上下穿过以及 "—"左右穿过不属于反射

#include<bits/stdc++.h>
using namespace std;

int n,m,q;
char g[1005][1005];
int ne1[4]={1,0,2,3};//'-'
int ne2[4]={0,1,3,2};//'|'
int ne3[4]={3,2,1,0};//'/'
int ne4[4]={2,3,0,1};//'\'
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};//上 下 左 右 = {0,1,2,3};
int in[1005][1005][4];//in[i][j][k]:以k方向射入(i,j)被不同镜子反射的次数
int dfn[1005][1005][4];//dfn序判环
bool st[1005][1005];//标记当前镜子已反射过
bool in_st[1005][1005][4];//标记此状态已存在答案

int idx=0;
struct st{
    int x,y,k,flag;
}a[4000005];//最多4*n*m个状态
map<pair<int,int>,int> h;

void dfs_line(int x,int y,int k)//搜索处理链
{
    if(x<1 || y<1 || x>n || y>m)return ;//边界
    
    //当前镜子直接穿过不反射的情况
    int flag=1;
    if(g[x][y]=='|' && (k==0 || k==1))flag=0;
    if(g[x][y]=='-' && (k==2 || k==3))flag=0;
    
    int nx=x,ny=y,nk=k;
    if(g[x][y]=='-')nk=ne1[k],nx+=dx[nk],ny+=dy[nk];
    if(g[x][y]=='|')nk=ne2[k],nx+=dx[nk],ny+=dy[nk];
    if(g[x][y]=='/')nk=ne3[k],nx+=dx[nk],ny+=dy[nk];
    if(g[x][y]=='\\')nk=ne4[k],nx+=dx[nk],ny+=dy[nk];
    
    a[++idx]={x,y,k,flag};//将路径存在a数组中
    dfs_line(nx,ny,nk);
    return ;
}

void get_in()//处理光链上的答案
{
    int cnt=0;
    for(int i=idx;i>=1;i--)
    {
        if(a[i].flag && h[{a[i].x,a[i].y}]==0)
        {
            cnt++;
            h[{a[i].x,a[i].y}]++;
        }
        in[a[i].x][a[i].y][a[i].k]=cnt;
        in_st[a[i].x][a[i].y][a[i].k]=true;
    }
}

int dfs_loop(int x,int y,int k)//搜索处理环
{
    //当前镜子直接穿过不反射的情况和重复镜子反射的情况不贡献答案
    int flag=1;
    if(st[x][y] || (g[x][y]=='|' && (k==0 || k==1)))flag=0;
    if(st[x][y] || (g[x][y]=='-' && (k==2 || k==3)))flag=0;
    if(flag==1)st[x][y]=true;//标记此镜子已经反射过了
    
    int nx=x,ny=y,nk=k;
    if(g[x][y]=='-')nk=ne1[k],nx+=dx[nk],ny+=dy[nk];
    if(g[x][y]=='|')nk=ne2[k],nx+=dx[nk],ny+=dy[nk];
    if(g[x][y]=='/')nk=ne3[k],nx+=dx[nk],ny+=dy[nk];
    if(g[x][y]=='\\')nk=ne4[k],nx+=dx[nk],ny+=dy[nk];
    
    int n0=dfn[x][y][k],n1=dfn[nx][ny][nk];
    if(n1!=0 && n1<=n0)in[x][y][k]=n0+flag-1;//找到环了
    else//没找到环
    {
        dfn[nx][ny][nk]=dfn[x][y][k]+flag;
        in[x][y][k]=dfs_loop(nx,ny,nk);
    }
    
    st[x][y]=false;//恢复,一个镜子可能参与多个环的反射
    in_st[x][y][k]=true;
    return in[x][y][k];
}

void solved()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>g[i][j];
    
    //离线处理链
    for(int i=1;i<=n;i++)
    {
        h.clear(),idx=0;
        dfs_line(i,1,3);
        get_in();
        
        h.clear(),idx=0;
        dfs_line(i,m,2);
        get_in();
    }
    for(int i=1;i<=m;i++)
    {
        h.clear(),idx=0;
        dfs_line(1,i,1);
        get_in();
        
        h.clear(),idx=0;
        dfs_line(n,i,0);
        get_in();
    }
    
    //处理环
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<4;k++)
            {
                if(in_st[i][j][k])continue;
                dfn[i][j][k]=1;//起点标为1
                dfs_loop(i,j,k);
            }
            
    cin>>q;
    while(q--)
    {
        int x,y,k;
        string s;
        cin>>x>>y>>s;
        if(s=="above")k=0;
        if(s=="below")k=1;
        if(s=="left")k=2;
        if(s=="right")k=3;
        int nx=x+dx[k],ny=y+dy[k];
        cout<<in[nx][ny][k]<<endl;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    solved();
    return 0;
}

题解 | #Mirror Maze#

I题