1.题目描述
Young Tableau 是满足如下定义的二维数表：
- 所有行均为左对齐，所有行的最左端在同一列，且每一行均连续无空位；
- 从上到下每一行的列数非严格单调递减；
- 每一行中的数从左到右严格单调递增；
- 每一列中的数从上到下严格单调递增。
请编写一个程序，判断一个数表是否是Young Tableau。数表的行数和列数至多为10，所有数均为正整数。
- 输入样例：
是Young Tableau，而1 2 3 4 5 6
和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.题目解析
- 预备知识
- 严格递减表示
< - 非严格递减表示
=< - 不定长数据表示
- 【C方式】通常使用一个定长数组，非法数字表示行和列的结束。
- 【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;
}
}
