CDOJ1621 PaPaPa

 

　　题目地址：http://acm.uestc.edu.cn/problem.php?pid=1621

　　题目分析：一个二维字符数组（作者好像说a code rectangle），含有如下字符：

　　作者定义了一种好怪的执行代码的方式：

　　1. 从左上点开始，最开始往右走；

　　2. 如果碰到'v','>','<','^'就改变走的方向；

　　3. 碰到'@'就结束；

　　4. 碰到大写英文字母就输出来；

　　5. 如果出现循环就停止，并在输出时，把循环的内容用[]框上；

　　6. 走出界就结束。

      解题思路：其实这题还是蛮简单的模拟题。下面简要的列些要点：

      1. 用一个数组route来存走过的路径；

      2. 用一个三维数组来标记走过的点（为什么要三维呢？二维数组就可以确定一个点了，我们用第三维存走过该点时的行动方向！因为要判循环嘛，可是仅仅是走上同一个点，但两次走的方向不同就不是出现循环哦～），数组map[i][j][k]，记录以方向k走过该点时将该点内容存在route中的下标；

      3. 设置一个全局变量dir标记走的方向；

      4. 设置一个信号量isCircle，初始化为-1，若出现循环（map[i][j][dir]!=-1）isCircle=map[i][j][dir]（还记得map中存的什么吗？）

      5. 遇到'@'，或走出界或循环了就结束；

      6. 输出。若isCircle==-1，没什么问题吧？若isCircle!=-1，先输出route：[0～iscircle-1]，输出'['，输出route：[isCircle～end]，输出']\n'；（如果你不明白，回过去看看我们isCircle记录了什么。）

　　源代码：

    #include<cstdio>
    #include<cstring>
    #define PN printf("\n");

    char chret;
    #define SCRN while(scanf("%c",&chret) && chret!='\n');
    
    int n,m;
    string pro[200];
    Int map[200][200][4],top,dir,isCircle,x,y;//dir==1:right; dir==2:down; dir==3:left; dir=4:up;
    char route[40000];
    
    void ini()
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                map[i][j][0]=-1;
                map[i][j][1]=-1;
                map[i][j][2]=-1;
                map[i][j][3]=-1;
            }
    }
    
    void letsGo()
    {
        while(isCircle==-1 && x>=0 && x<n && y>=0 && y<m)
        {
            if(map[x][y][dir-1]>-1)
            {
                isCircle=map[x][y][dir-1];
                return ;
            }
            if(pro[x][y]=='@')
                return ;
            map[x][y][dir-1]=top;
            route[top++]=pro[x][y];
            if(pro[x][y]=='>')
                dir=1;
            else if(pro[x][y]=='<')
                dir=3;
            else if(pro[x][y]=='v')
                dir=2;
            else if(pro[x][y]=='^')
                dir=4;
            if(dir==1)
                y++;
            else if(dir==2)
                x++;
            else if(dir==3)
                y--;
            else if(dir==4)
                x--;
        }
        return ;
    }
    
    int main()
    {
        int T,i;
        //freopen("Din.txt","r",stdin);
        scanf("%d",&T);
        while(T--)
        {
            cin>>n>>m;
            SCRN
            for(i=0;i<n;i++)
                cin>>pro[i];
            ini();
            top=0;
            dir=1;
            isCircle=-1;
            x=0;
            y=0;
            letsGo();
            if(isCircle==-1)
            {
                for(i=0; i<top; i++)
                    if(route[i]!='v' && route[i]!='^' && route[i]!='<' && route[i]!='>')
                        printf("%c",route[i]);
                PN
            }
            else
            {
                for(i=0;i<isCircle;i++)
                    if(route[i]!='v' && route[i]!='^' && route[i]!='<' && route[i]!='>')
                        printf("%c",route[i]);
                printf("[");
                for(;i<top;i++)
                    if(route[i]!='v' && route[i]!='^' && route[i]!='<' && route[i]!='>')
                        printf("%c",route[i]);
                printf("]");
                PN
            }
        }
        return 0;
    }