POJ1420 Spreadsheet(拓扑排序)注意的是超内存

Spreadsheet
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 617   Accepted: 290

Description

In 1979, Dan Bricklin and Bob Frankston wrote VisiCalc, the first spreadsheet application. It became 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 spreadsheets. 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. 

 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 

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,
AAC, … 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.

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

Source

Southwestern European Regional Contest 1995
题意:列的名称是: A, B, C, …, Z, AA, AB, AC, …, AZ, BA, …, BZ, CA, … ZZ, AAA, AAB, AAC, … AAZ, ABA, …, ABZ, ACA, …, ZZZ。行的名称是1~999。现在给了1个矩阵,每一个格子里要末是数要末是表达式(=A1+A2表示当前格子的数=第1行第1列的数+第1行第2列的数),求出所有格子的数,保证有答案。
解题:这就是拓扑排序,主要是处理建图,且注意内存分配。
#include<stdio.h>
#include<string>
#include<queue>
#include<iostream>
using namespace std;
const int N = 1005;
const int M = 26+26*26+26*26*26;

int num[N][M],n,m,in[N*M];
vector<vector<int> >mapt;

void topeSort()
{
queue<int>q;
int s;
for(int i=0;i<n*m;i++)
if(in[i]==0)
q.push(i);
while(!q.empty())
{
s=q.front(); q.pop();
int len=mapt[s].size();
for(int i=0;i<len;i++)
{
int v=mapt[s][i];
in[v]–;
num[v/m][v%m]+=num[s/m][s%m];
if(in[v]==0)
q.push(v);
}
}
}

void build(const string &s,int i,int j)
{
int len=s.length(),ans=0;
if(s[0]>='0'&&s[0]<='9')
{
for(int ti=0;ti<len;ti++)
ans=ans*10+s[ti]-'0';
num[i][j]+=ans;
}
else
{
int r=0,l,ti,tj;
while(r<len)
{
r++;
if(s[r]>='0'&&s[r]<='9')
{
ans=0;
while(s[r]>='0'&&s[r]<='9'&&r<len){
ans=ans*10+s[r]-'0'; r++;
}
num[i][j]+=ans;
continue;
}
l=r;
while(s[r]>='A'&&s[r]<='Z')r++;
if(r-l==1) tj=s[l]-'A';
else if(r-l==2) tj=26+(s[l]-'A')*26+s[l+1]-'A'⑴;
else tj=26+26*26+(s[l]-'A')*26*26+(s[l+1]-'A')*26+s[l+2]-'A'⑴;

ti=0;
while(s[r]>='0'&&s[r]<='9'&&r<len){
ti=ti*10+s[r]-'0'; r++;
}
ti–;

mapt[ti*m+tj].push_back(i*m+j); in[i*m+j]++;//每一个2维位置(i,j)用1个数 i*m+j 表示
}
}
}
int main()
{
int t;
string str;
scanf("%d",&t);
while(t–)
{
scanf("%d%d",&m,&n);

mapt=vector<vector<int> >(n*m,vector<int>(0,0));
for(int i=0;i<=n*m;i++)
in[i]=0,mapt[i].clear();
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
num[i][j]=0;

for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>str;
build(str,i,j);
}
topeSort();
for(int i=0;i<n;i++)
{
printf("%d",num[i][0]);
for(int j=1;j<m;j++)
printf(" %d",num[i][j]);
printf("
");
}

}
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » POJ1420 Spreadsheet(拓扑排序)注意的是超内存

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡