POJ1420 Spreadsheet（拓撲排序）注意的是超內存
來源：程序員人生 發布時間：2015-06-05 09:21:19 閱讀次數：3761次
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("
");
}
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
