判断出栈序列合法性

描述

有1、2、3、4、5、6、7这7个数字依次全部入栈后再出栈，在入栈的过程中栈中的数据也可以随时出栈，一直到整个栈为空。将出栈得到的数字依次排列，就可以得到一个“合法”的序列；对应的，有些形式字的排列是无论如何调整入栈和出栈顺序也无法得到的，被称为“非法”序列。

比如：“1 2 3 4 6 7 5” 和“1 2 5 6 4 3 7”都是合法的序列，而“1 2 5 7 3 4 6”和“1 2 6 3 4 5 7”以及“1 2 6 3 5 4 7”都是非法的序列。

请编写程序，判断给定的由7个数字组成的序列是合法的还是非法的，如果是合法的输出“Y”，否则输出“N”。

格式

输入格式

第1行是一个整数n，表示要判断的序列的数目。
从第2行到第n+1行，每行一个序列，由1~7组成

输出格式

输出为一行，一个由“Y”和“N”组成的长度为n的字符串，中间不要空格

样例

输入样例

5
1 2 6 3 5 7 4
1 2 6 5 3 7 4
1 2 7 4 5 6 3
1 2 7 6 3 4 5
1 3 2 4 5 7 6

输出样例

NNNNY

限制

时间限制：100 ms
内存限制：16384 KB

代码

//判断依据：出栈序列中，元素i之后所有比i小的元素间必须是降序排列的。
#include<stdio.h>
#define Size 7
int main()
{
    int n;
    scanf("%d", &n);
    int cur[100][Size];//二位数组前部分标记测试样例数，后部分表示每个样例中的数序号
    int x;
    //赋值
    for (x = 1; x <= n; x++)
    {
        int y;
        for (y = 0; y < Size; y++)
        {
            scanf("%d", &(cur[x][y]));
        }
    }
    int i, j, k, t, q;
    int temp, flag1, flag2;
    q = 1;
    a:
    while( q <= n)
    {
        for (j = 0; j < Size; j++)
        {
            flag1 = 0;
            flag2 = 0;
            for (k = j + 1; k < Size; k++) //寻找s[i]之后第一个比s[i]小的    (!!!!!)
            {
                if (cur[q][k] < cur[q][j])//s[i]之后存在比s[i]小的
                {
                    temp = cur[q][k];//s[j]是s[i]之后第一个比s[i]小的
                    flag1 = 1;
                    break;
                }
            }
            if (flag1 == 1)
            {
                for (t = k + 1; t < Size; t++)
                {
                    if (cur[q][t] < cur[q][j])//s[j]之后如果还有比s[i]小的数
                    {
                        if (cur[q][t] < temp)//都必须小于它之前的一个比s[i]小的数
                        {
                            temp = cur[q][t];//并更新temp
                        }
                        else//否则，出栈序列非法
                        {
                            flag2 = 1;
                            break;//退出至（！！！！！）循环
                        }
                    }
                }
            }
            if (flag2 == 1)//接着退出循环
            {
                break;
             }
        }
        if (flag2 == 1)
        {
            printf("N");
            if (q!= n)
            {
                q++;
                goto a;
            }
        }
        else
        {
            printf("Y");
            if (q != n)
            {
                q++;
                goto a;
            }
        }
        q++;
    }
    printf("\n");
return 0;
}