POJ1420 Spreadsheet(拓扑排序)注意的是超内存
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了POJ1420 Spreadsheet(拓扑排序)注意的是超内存,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4929字,纯文字阅读大概需要8分钟。
内容图文
![POJ1420 Spreadsheet(拓扑排序)注意的是超内存](/upload/InfoBanner/zyjiaocheng/1196/7d9e5648ec1744cabe16b13ef65a1bca.jpg)
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 617 | Accepted: 290 |
Description
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
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
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
#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'-1; else tj=26+26*26+(s[l]-'A')*26*26+(s[l+1]-'A')*26+s[l+2]-'A'-1; 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]++;//每个二维位置(i,j)用一个数 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("\n"); } } }
原文:http://blog.csdn.net/u010372095/article/details/45372025
内容总结
以上是互联网集市为您收集整理的POJ1420 Spreadsheet(拓扑排序)注意的是超内存全部内容,希望文章能够帮你解决POJ1420 Spreadsheet(拓扑排序)注意的是超内存所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。