UVa 500 Table
题目描述
题目要求将使用伪图形字符绘制的表格进行自动对齐。表格由横线（-，ASCII 196\texttt{ASCII 196}ASCII 196）、竖线（|，ASCII 179\texttt{ASCII 179}ASCII 179）和角点字符（如┌、┐、└、┘、┬、┴、┼、├、┤等）组成。表格中的单元格文本可能分布在多行中。对齐后，每个单元格的内容与左右竖线之间应满足：左边恰好一个空格，右边至少一个空格。目标是使表格的总宽度（即每行长度）最小化。
输入格式
第一行一个整数MMM，表示数据集的个数，后面跟一个空行。每个数据集包含一个已编辑的表格，表格行数不超过100100100，每行长度不超过255255255字符。输入行本身不含前导和尾随空格，也不含空行。两个连续数据集之间由一个空行分隔。
输出格式
对于每个数据集，输出对齐后的表格。输出行不应包含前导和尾随空格，也不应有空行。格式化后表格的宽度不超过255255255字符。两个连续数据集的输出之间由一个空行分隔。
样例
输入
1 ┌───────────────┬─────────────┬────────────────────────────────────────┐ │Name │Organization │JOB │ ├───────────────┼─────────────┼────────────────────────────────────────┤ │Bill Clinton │USA │The President of the United States │ │Bill Gates │Microsoft Corporation│President │ │Bill Poucher │A C M │International Collegiate Programming Contest Director│ └───────────────┴─────────────┴────────────────────────────────────────┘输出
┌──────────────┬──────────────────────┬────────────────────────────────────────────────────────────┐ │Name │Organization │JOB │ ├──────────────┼──────────────────────┼────────────────────────────────────────────────────────────┤ │Bill Clinton │USA │The President of the United States │ │Bill Gates │Microsoft Corporation │President │ │Bill Poucher │A C M │International Collegiate Programming Contest Director │ └──────────────┴──────────────────────┴────────────────────────────────────────────────────────────┘题目分析
本题的核心是解析由伪图形字符构成的表格，计算每列所需的最小宽度，然后重新绘制表格。
表格结构
表格由以下字符构成：
- 横线：
-（ASCII 196\texttt{ASCII 196}ASCII 196） - 竖线：
|（ASCII 179\texttt{ASCII 179}ASCII 179） - 十字交叉点：
┼（ASCII 197\texttt{ASCII 197}ASCII 197） - 角点：
┌（218\texttt{218}218）、┐（191\texttt{191}191）、└（192\texttt{192}192）、┘（217\texttt{217}217） - 三叉连接：
┬（194\texttt{194}194）、┴（193\texttt{193}193）、├（195\texttt{195}195）、┤（180\texttt{180}180）
表格的第一行以┌开始，最后一行以└开始。中间的行以├或|开始。
列宽计算
表格中每列由竖线分隔，竖线之间的内容为单元格文本。单元格文本可能分布在多行中。对于每列，需要找出该列所有单元格中非空内容的最大宽度（去除前导和尾随空格后的长度）。最终列宽即为该最大宽度。
对齐规则
- 每个单元格内容与左侧竖线之间恰好有一个空格。
- 每个单元格内容与右侧竖线之间至少有一个空格（即右侧填充空格数量为
列宽 - 内容长度 + 1）。 - 为最小化表格总宽度，每列宽度取该列所有单元格内容的最大长度。
绘制表格
根据计算出的列宽，重新绘制表格：
- 绘制顶部边框：
┌+ 若干-+┬+ … +┐ - 绘制分隔行：
├+ 若干-+┼+ … +┤ - 绘制底部边框：
└+ 若干-+┴+ … +┘ - 绘制数据行：
|+ 空格 + 单元格内容 + 若干空格 +|+ …
算法步骤
- 读取整个表格，按行存储。
- 扫描表格，识别所有包含竖线的行（即
|开头的行），解析每行的单元格内容。 - 对于每列，统计所有单元格内容去除前导和尾随空格后的长度，取最大值作为该列宽度。
- 根据列宽重新绘制表格：
- 绘制顶部边框。
- 绘制数据行（保留原始单元格内容的顺序）。
- 绘制分隔行（根据原始表格中的分隔行位置决定是否绘制，但题目要求保持原始行数不变？实际上，原始表格的每行（包括横线行）都应保留，但横线行需根据新列宽重新绘制）。
- 输出结果。
复杂度分析
表格行数R≤100R \le 100R≤100，列数C≤256C \le 256C≤256，每行长度≤255\le 255≤255，总复杂度O(R×C)O(R \times C)O(R×C)。
代码实现
// Table// UVa ID: 500// Verdict: Accepted// Submission Date: 2017-04-17// UVa Run Time: 0.100s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constcharseparator=(char)(179),right_line_separator=(char)(180),top_right_corner=(char)(191),bottom_left_corner=(char)(192),bottom_line_separator=(char)(193),top_line_separator=(char)(194),left_line_separator=(char)(195),link=(char)(196),middle_line_separator=(char)(197),bottom_right_corner=(char)(217),top_left_corner=(char)(218);voiddrawLine(intcolumns,vector<int>&columnWidth,charleftChar,charmiddleChar,charrightChar){cout<<leftChar;for(inti=0;i<columns;i++){if(i>0)cout<<middleChar;for(intj=0;j<columnWidth[i]+2;j++)cout<<link;}cout<<rightChar<<'\n';}voidprocess(vector<string>&table){vector<int>columnWidth(256,0);intcolumns=0;for(inti=0;i<table.size();i++)if(table[i].front()==separator){istringstreamiss(table[i].substr(1,table[i].length()-1));string block;intc=0;while(getline(iss,block,separator)){intii=0,jj=block.length()-1;while(ii<block.length()&&isblank(block[ii]))ii++;while(jj>=0&&isblank(block[jj]))jj--;if(ii<=jj)columnWidth[c]=max(columnWidth[c],jj-ii+1);c++;}columns=c;}for(inti=0;i<table.size();i++){if(table[i].front()==top_left_corner)drawLine(columns,columnWidth,top_left_corner,top_line_separator,top_right_corner);if(table[i].front()==bottom_left_corner)drawLine(columns,columnWidth,bottom_left_corner,bottom_line_separator,bottom_right_corner);if(table[i].front()==left_line_separator)drawLine(columns,columnWidth,left_line_separator,middle_line_separator,right_line_separator);if(table[i].front()==separator){istringstreamiss(table[i].substr(1,table[i].length()-1));string block;intc=0;while(getline(iss,block,separator)){intii=0,jj=block.length()-1;while(ii<block.length()&&isblank(block[ii]))ii++;while(jj>=0&&isblank(block[jj]))jj--;if(ii<=jj)block=block.substr(ii,jj-ii+1);elseblock.clear();cout<<separator<<' '<<block;cout<<string(columnWidth[c]+1-block.length(),' ');c++;}cout<<separator<<'\n';}}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcases=stoi(line);getline(cin,line);for(intc=1;c<=cases;c++){if(c>1)cout<<'\n';vector<string>table;while(getline(cin,line),line.length()>0)table.push_back(line);process(table);}return0;}