[04无验证]Young Tableau-七牛云2018秋

1.题目描述

Young Tableau 是满足如下定义的二维数表：

1. 所有行均为左对齐，所有行的最左端在同一列，且每一行均连续无空位；
2. 从上到下每一行的列数非严格单调递减；
3. 每一行中的数从左到右严格单调递增；
4. 每一列中的数从上到下严格单调递增。
   请编写一个程序，判断一个数表是否是Young Tableau。数表的行数和列数至多为10，所有数均为正整数。

• 输入样例：

  1 2 3 
  4 5 
  6 
  

  是Young Tableau，而

  1 3 2 
  4 5 
  6 
  

  和

  1 4 5 
  2 3 
  6 
  

  都不是。
• 输入格式:
  每组测试数据包含多个测试点，输入的第一行表示测试点的数量（至多5 组）。
  每个测试点是一个二维数表，输入中的每一行表示数表的一行，不同的数之间用一个空格隔开。 测试点之间用一个空行隔开。例如

  2 
  1 3 4 5 6 
  2 7 10 
  8 9
  
  2 5 8 9 
  7 11 10
  

• 输出格式:
  针对每一个测试点输出一行，内容为true/false（全部小写）表示是/不是Young Tableau。例如

  true 
  false
  

2.题目解析

• 预备知识
  • 严格递减表示<
  • 非严格递减表示=<
  • 不定长数据表示
    1. 【C方式】通常使用一个定长数组，非法数字表示行和列的结束。
    2. 【C++方式】使用嵌套vector。

本题目就是二维循环简单遍历。

3.参考答案

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

bool IsYoungTableau(vector<vector<int>> nums){
    if(nums.empty())return false; 
    for(int i=1;i!=nums.size();++i){
        for(int j=1;j!=nums[i].size();++j){
            // 右边的数必须大于左边的数
            if (nums[i][j] < nums[i][j-1]) return false; 
            // 下边的数必须大于上边的数
            if (nums[i][j] < nums[i-1][j]) return false;
        }
        // 当前行长度要小于等于上一行
        if (nums[i].size() > nums[i-1].size()) return false;
    }
    return true;
}

int main(){
  int n = 0;
  scanf("%d\n",&n); // 这里\n防止被cin读入
  bool res[n];
  for(int i=0;i!=n;++i){
      vector<vector<int> > nums;
      string str; // 保存一行数据
      while(getline(cin,str,'\n')){ // 读取一行数据
        if(str.empty()) break; // 空行退出
        istringstream iss(str);
        int num = 0;
        vector<int> temp;
        while(iss >> num){ // 取出一行数据中的数字
            temp.push_back(num);
        }
        nums.push_back(temp);
      }
      res[i] = IsYoungTableau(nums);
  }
  // 打印结果
  for(int i=0;i!=n;++i){
    cout << boolalpha << res[i] << endl;
  }
}