uva 196 Spreadsheet
原题:
In 1979, Dan Bricklin and Bob Frankston wrote VisiCalc, the first spreadsheet application. It be-
came a huge success and, at that time, was the killer application for the Apple II computers. Today,
spreadsheets are found on most desktop computers.
The idea behind spreadsheets is very simple, though powerful. A spreadsheet consists of a table
where each cell contains either a number or a formula. A formula can compute an expression that
depends on the values of other cells. Text and graphics can be added for presentation purposes.
You are to write a very simple spreadsheet application. Your program should accept several spread-
sheets. Each cell of the spreadsheet contains either a numeric value (integers only) or a formula, which
only support sums. After having computed the values of all formulas, your program should output the
resulting spreadsheet where all formulas have been replaced by their value.
Input
The first line of the input file contains the number of spreadsheets to follow. A spreadsheet starts with
a line consisting of two integer numbers, separated by a space, giving the number of columns and rows.
The following lines of the spreadsheet each contain a row. A row consists of the cells of that row,
separated by a single space.
A cell consists either of a numeric integer value or of a formula. A formula starts with an equal sign
(=). After that, one or more cell names follow, separated by plus signs (+). The value of such a formula
is the sum of all values found in the referenced cells. These cells may again contain a formula. There
are no spaces within a formula.
You may safely assume that there are no cyclic dependencies between cells. So each spreadsheet
can be fully computed.
The name of a cell consists of one to three letters for the column followed by a number between 1
and 999 (including) for the row. The letters for the column form the following series: A, B, C, …, Z,
AA, AB, AC, …, AZ, BA, …, BZ, CA, …, ZZ, AAA, AAB, …, AAZ, ABA, …, ABZ, ACA, …, ZZZ.
These letters correspond to the number from 1 to 18278. The top left cell has the name ‘A1’.
See Figure 1.
A1 B1 C1 D1 E1 F1 …
A2 B2 C2 D2 E2 F2 …
A3 B3 C3 D3 E3 F3 …
A4 B4 C4 D4 E4 F4 …
A5 B5 C5 D5 E5 F5 …
A6 B6 C6 D6 E6 F6 …
… … … … … … …
Figure 1: Naming of the top left cells
Output
The output of your program should have the same format as the input, except that the number of
spreadsheets and the number of columns and rows are not repeated. Furthermore, all formulas should
be replaced by their value.
Sample Input
1
4 3
10 34 37 =A1+B1+C1
40 17 34 =A2+B2+C2
=A1+A2 =B1+B2 =C1+C2 =D1+D2
Sample Output
10 34 37 81
40 17 34 91
50 51 71 172
中文:
给你一个表格,有的表格是数字,有的表格是表达式,如果某一个格当中是表达式,那么该单元的值由表达式决定。表示由表格中其他单元格中的值的和组成,现在让你计算出所有表格的值是多少。
attention!
数据中的列大小不会超过1000,与题目中的描述不符。
输入数据为先输入列,后输入行。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,m,t;
string table[1005][2000];
int ans[1005][2000];
int dfs(int x,int y)
{
if(ans[x][y]!=INT_MAX)
return ans[x][y];
if(table[x][y][0]!='=')
return ans[x][y]=stoi(table[x][y]);
int r=0,c=0,res=0;
for(int i=1;i<=table[x][y].size();i++)//i等于sheet[x][y].size会去执行dfs
{
if(isdigit(table[x][y][i]))
r=r*10+table[x][y][i]-'0';
else
{
if(isalpha(table[x][y][i]))
c=c*26+table[x][y][i]-'A'+1;
else
{
res+=dfs(r,c);
r=c=0;
}
}
}
return ans[x][y]=res;
}
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
cin>>m>>n;
string s;
memset(ans,0,sizeof(ans));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>table[i][j];
ans[i][j]=INT_MAX;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
ans[i][j]=dfs(i,j);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j!=m)
cout<<ans[i][j]<<" ";
else
cout<<ans[i][j]<<endl;
}
}
}
return 0;
}
解题思路:
在纸上画一画可以看出此题目可以直接用搜索去完成,在搜索某一个单元格的表达式的过程中可以将途径的单元格顺便保存好,即使用记忆化搜索的方法实现。
当然,此题也可以使用拓扑排序来完成。
上一篇: 1075 链表元素分类 (25分)
下一篇: 对图片md5加密实现
推荐阅读
-
团体队列 UVA540 Team Queue
-
丑数(Ugly Numbers, UVa 136)
-
破损的键盘(悲剧文本)(Broken Keyboard(a.k.a. Beiju Text),Uva 11988)
-
集合栈计算机(The SetStack Computer, ACM/ICPC NWERC 2006,Uva12096)
-
唯一的雪花(Unique snowflakes,UVa 11572)滑动窗口+set
-
Google Spreadsheet Add-on Links Extractor 谷歌表格插件链接提取器的制作与发布(附源码)
-
爆笑之逗B剧场第196季
-
[UVA - 11584] Partitioning by Palindromes dp预处理
-
[LeetCode] 196.删除重复的电子邮箱
-
UVA227-Puzzle