题意:给出一个表格,一部分单元格是给定的数字,而另一部分单元格则是一个式子,表示是其他一些单元格的和,让你输出最后计算出的所有格子的数。
因为有些格子需要其他格子先计算出来,所以计算顺序是按照拓扑序的,只不过题意给出的表格大小非常恐怖……貌似是 1e9 级别的单元格数……后来看了discuss才知道数据只有100*100……然后就是读入了,我本来以为读入会很烦,后来写写才发现其实也挺容易的。然后就是排拓扑序并计算就行了。
1 #include<stdio.h>
2 #include<string.h>
3 #include<queue>
4 using namespace std;
5
6 char s[1000];
7 int num[205][205],id[40000];
8 int head[40000],point[40000],nxt[40000],size;
9 int n,m;
10
11 void add(int a,int b){
12 point[size]=b;
13 nxt[size]=head[a];
14 head[a]=size++;
15 id[b]++;
16 }
17
18 void getnum(int a,int b){
19 for(int i=0;s[i];++i){
20 num[a][b]=num[a][b]*10+s[i]-'0';
21 }
22 }
23
24 void getedge(int a,int b){
25 int aa=0,bb=0;
26 for(int i=1;s[i];++i){
27 if(s[i]>='A'&&s[i]<='Z'){
28 aa=aa*26+s[i]-'A'+1;
29 }
30 else if(s[i]>='0'&&s[i]<='9'){
31 bb=bb*10+s[i]-'0';
32 }
33 else if(s[i]=='+'){
34 add((bb-1)*m+aa,(a-1)*m+b);
35 aa=0;
36 bb=0;
37 }
38 }
39 add((bb-1)*m+aa,(a-1)*m+b);
40 }
41
42 void topo(){
43 queue<int>q;
44 for(int i=1;i<=n*m;++i)if(!id[i])q.push(i);
45 int cnt=0;
46 while(!q.empty()){
47 int u=q.front();
48 q.pop();
49 int a=u/m,b=u%m;
50 if(b)a++;
51 else b=m;
52 cnt++;
53 for(int i=head[u];~i;i=nxt[i]){
54 int j=point[i];
55 id[j]--;
56 int aa=j/m,bb=j%m;
57 if(bb)aa++;
58 else bb=m;
59 num[aa][bb]+=num[a][b];
60 if(!id[j])q.push(j);
61 }
62 }
63 }
64
65 int main(){
66 int T;
67 scanf("%d",&T);
68 while(T--){
69 memset(num,0,sizeof(num));
70 memset(id,0,sizeof(id));
71 memset(head,-1,sizeof(head));
72 size=0;
73 scanf("%d%d",&m,&n);
74 for(int i=1;i<=n;++i){
75 for(int j=1;j<=m;++j){
76 scanf("%s",s);
77 if(s[0]=='=')getedge(i,j);
78 else getnum(i,j);
79 }
80 }
81 topo();
82 for(int i=1;i<=n;++i){
83 for(int j=1;j<=m;++j){
84 printf("%d",num[i][j]);
85 if(j==m)printf("
");
86 else printf(" ");
87 }
88 }
89 }
90 return 0;
91 }