炫酷镜子（C++）

点击做题网站链接

题目描述
小希拿到了一个镜子块，镜子块可以视为一个N x M的方格图，里面每个格子仅可能安装\或者/的镜子,会反射90°光线，也可能没有安装镜子，使用.代替。
但她看不清楚里面的镜子构造是怎样的。
你是这块镜子块的主人，所以你想计算这块镜子块（从输入的上方往下射入光线）从左到右每一格射入依次分别会从最下面的哪一格子射出，如果无法射出，输出-1。

输入描述:
第一行输入两个整数N,M。随后的N行，每行M个字符。
1≤N,M≤500

输出描述:
输出M行整数，依次为从第i个格子从上往下射入时从下面的哪里射出，如果光线不会从下面射出，则输出-1。

示例1
输入
3 3

...
...
\.\

输出
3
2
-1

说明
第一列遇到镜子两次反弹通过第三列射出。
第二列直接射出。
第三列因为镜子反弹后向右边射出。

题目思路：

一道非常有意思的题目，让我想到了一些手机小游戏的设计。
直接模拟即可，或者使用并查集或者记忆化搜索也可。
时间复杂度O(NM)

解题代码：

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    char a[505][505];
    int dx[4][2]={-1,0,//第一列是对应于x（纵向坐标变化）
                   1,0,//第二列是对应于y（横向坐标变化）
                   0,-1,
                   0,1};
    int change[2][4]={3,2,1,0,//这是一个协助dir改变方向的数组
                      2,3,0,1};//第一行是如果碰到'/'镜子，第二行是如果碰到'\'镜子
    cin >> n >> m;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            cin >> a[i][j];
    
    for(int i=1;i<=m;++i)
    {
        int x=0,y=i,dir=1;//dir：1下，2左，3右，4上
        while(1)
        {
            x += dx[dir][0];//纵向的行进
            y += dx[dir][1];//横向的行进
            if( x>n ) break;//如果纵向超过下边界
            else if( x<1 || y<1 || y>m )//如果纵向超过上边界，或横向超过左边界，或横向超过右边界
            {
                y=-1;//光线不会从下面射出
                break;
            }
            else//在范围内
            {
                if( a[x][y]=='/' )//如果碰到'/'镜子
                    dir = change[0][dir];//改变方向，变为向左或向下
                else if( a[x][y]=='\\' )//如果碰到'\'镜子
                    dir = change[1][dir];//改变方向，变为向右或向上
            }
        }
        cout << y << endl;
    }
}