UVa 196 Spreadsheet

题目分析本题要求实现一个简单的电子表格计算程序。电子表格由若干单元格组成每个单元格要么是一个整数数值要么是一个求和公式。公式以等号开头后面跟着若干用加号连接的单元格引用表示这些单元格数值的总和。题目保证没有循环依赖因此所有单元格都可以被正确计算。输入的第一行是电子表格的数量。每个电子表格的第一行包含两个整数列数和行数。接下来是表格的每一行数据行内的单元格用空格分隔。输出的格式与输入相同但所有公式都要替换为计算后的数值。难点单元格命名规则不是简单的A1, B1, ... , Z1, AA1, AB1, ...这样的 26 进制表示而是类似于 Excel 的列命名方式其中A对应111Z对应262626AA对应272727依此类推最大为ZZZ对应182781827818278。解题思路1. 单元格命名转换需要实现两个转换从行列坐标(row, col)转换为单元格名称getCellId(row, col)从单元格名称解析出行列坐标本题用不到getCellId的实现采用262626进制转换但需要注意普通的262626进制中A对应000而本题中A对应111因此需要特殊处理当余数为000时对应字母Z并将商减111。2. 数据存储使用两个map结构cells存储已经计算出的单元格数值键为单元格名称值为整数formula存储公式的依赖关系键为单元格名称值为引用的单元格名称列表3. 递归计算getValue(x)函数采用类似深度优先搜索的方式计算单元格x的值如果x已经在cells中直接返回其数值否则x是一个公式遍历其依赖的所有单元格递归调用getValue求和将计算结果存入cells并返回由于题目保证无环递归可以正确终止。4. 输入解析读取每个单元格内容时如果以开头则解析公式在末尾添加作为哨兵然后用find定位的位置提取每个引用的单元格名称否则直接转换为整数存入cells5. 输出按行按列遍历所有单元格调用getValue获取计算结果并输出。代码实现// Spreadsheet// UVa ID: 196// Verdict: Accepted// Submission Date: 2016-03-15// UVa Run Time: 0.093s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;mapstring,intcells;// 存储已计算的单元格数值mapstring,vectorstringformula;// 存储公式的依赖关系string columnsZABCDEFGHIJKLMNOPQRSTUVWXY;// 列名映射索引 1~26 对应 A~Z// 将行列坐标转换为单元格名称例如 (1,1) - A1stringgetCellId(inti,intj){string id;while(j0){// 取余数columns[j % 26] 得到对应字母id.insert(id.begin(),columns[j%26]);// 当余数为 0 时表示 Z需要将 j 减去 26 以正确处理进位if(j%260)j-26;j/26;}returnidto_string(i);}// 递归计算单元格 x 的值intgetValue(string x){// 如果已经计算过直接返回if(cells.count(x))returncells[x];intsum0;// 遍历公式中引用的所有单元格递归求和for(inti0;iformula[x].size();i)sumgetValue(formula[x][i]);// 记忆化存储结果cells[x]sum;returnsum;}intmain(){cin.tie(0);cout.sync_with_stdio(false);intn;cinn;while(n--){introw,column;cincolumnrow;// 清空上一次的数据cells.clear();formula.clear();// 读取整个电子表格for(inti1;irow;i)for(intj1;jcolumn;j){string block;cinblock;string idgetCellId(i,j);// 判断是否为公式以等号开头if(block.front()){// 在末尾添加 作为哨兵方便解析block;intstart1,nextstart;while(startblock.length()){// 找到下一个 的位置nextblock.find(,start);// 提取两个 之间的单元格名称formula[id].push_back(block.substr(start,next-start));startnext1;}}else{// 数值直接存入 cellscells[id]stoi(block);}}// 输出结果for(inti1;irow;i){for(intj1;jcolumn;j)cout(j1? :)getValue(getCellId(i,j));cout\n;}}return0;}复杂度分析时间复杂度每个单元格最多被计算一次且每次计算需要遍历其引用的单元格总时间复杂度为O(R×C)O(R \times C)O(R×C)其中RRR和CCC分别为行数和列数。空间复杂度O(R×C)O(R \times C)O(R×C)用于存储所有单元格的数值和公式依赖关系。