UVa 215电子表格计算器(Spreadsheet Calculator)
发布时间
阅读量:
阅读量
题目:
假设提供一个表格,类似EXCEL的功能,要求计算出每个单元格的数值。若存在无法计算的单元格,则输出所有无法得出结果的单元格对应的原始表达式。
要点:
- 初看此题似乎与拓扑排序判断是否存在环有关,但实际情况是由于数据规模较小,似乎直接进行模拟即可。首先判断是否存在仅由数字单元格构成的表达式单元格,例如A0为1,A1=A0,则此时A1仅依赖数字单元格;而如果A2=A0+A2,则除了数字单元格外还包含非数字单元格A2。当计算出A1的值后,应将其值记录并标记为数字单元格。
- 由于数据量不大,可能无需使用拓扑排序方法,只需通过循环判断是否所有单元格都变为数字单元格即可。
不确定这种做法是否偏离了题目的初衷。最初打算采用拓扑排序来检测环结构,并以此作为切入点,但未能成功实现,最终选择暴力模拟的方法进行处理。因此拓扑排序判环的方法仍然保留下来。
以下代码相比其他实现方式更加易于理解。其核心是基于拓扑排序模板来判断是否存在环,并通过循环得到最终结果。
有兴趣的朋友也可以尝试移除拓扑排序部分,仅根据最终是否全部变为数字单元格来判断是否存在环结构。
#include<bits/stdc++.h>
using namespace std;
const int maxr = 20 + 5;
const int
全部评论 (0)
还没有任何评论哟~
