UVa 215 - Spreadsheet Calculator(DFS)

给出 n ∗ m 个单元格,可能是数据也可能是引用。若能计算出所有值,输出表格,否则输出不能算出的单元格。
对每个进行DFS,若出现环则无法计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<cctype>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=210;
int n,m,num;
int a[maxn];
bool loop,ok[maxn],vis[maxn];
string s[maxn];
struct node{
int id,sign;
node(int id=0,int sign=0):id(id),sign(sign){}
};
vector<node> ex[maxn];
int dfs(int cur){
if(!ok[cur]){
loop=true;
return 0;
}
if(ex[cur].empty()) return a[cur];
if(vis[cur]){
ok[cur]=false;
loop=true;
return 0;
}
vis[cur]=true;
for(int i=0;i<ex[cur].size();++i){
node& k=ex[cur][i];
if(ok[k.id]) a[cur]+=k.sign*dfs(k.id);
if(!ok[k.id]){
ok[cur]=false;
loop=true;
}
}
ex[cur].clear();
return a[cur];
}
int main(){
while(cin>>n>>m&&n&&m){
loop=false;
memset(a,0,sizeof(a));
memset(ok,1,sizeof(ok));
memset(vis,0,sizeof(vis));
int num=n*m;
for(int i=0;i<num;++i){
cin>>s[i];
string k=s[i];
vector<int> sign;
if(k[0]=='-') sign.push_back(-1);
else sign.push_back(1);
for(int j=0;j<k.length();++j){
if(k[j]=='-') sign.push_back(-1),k[j]=' ';
else if(k[j]=='+') sign.push_back(1),k[j]=' ';
}
stringstream ss(k);
int pos=0;
ex[i].clear();
while(ss>>k){
if(isdigit(k[0])){
istringstream tmp(k);
int cur;
tmp>>cur;
a[i]+=cur*sign[pos++];
}
else ex[i].push_back(node((k[0]-'A')*m+(k[1]-'0'),sign[pos++]));
}
}
for(int i=0;i<num;++i) dfs(i);
if(loop){
for(int i=0;i<num;++i)
if(!ok[i]) printf("%c%d: %s\n",i/m+'A',i%m,s[i].c_str());
}
else{
putchar(' ');
for(int i=0;i<m;++i) printf("%6d",i);
puts("");
for(int i=0;i<n;++i){
printf("%c",i+'A');
for(int j=0;j<m;++j) printf("%6d",a[i*m+j]);
puts("");
}
}
puts("");
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **