Advertisement

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)

还没有任何评论哟~