Spreadsheet
题目链接：
http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=17335
题目大意：
有一张类似于Excel的表格，其中编号如下：
现在在这些单元格中填入内容，可以为数字，也可以为字符串，其中字符串的格式必须为“=（）+（）……”。
如以下一个例子：
4 3 10 34 37 =A1+B1+C1 40 17 34 =A2+B2+C2 =A1+A2 =B1+B2 =C1+C2 =D1+D2保证这些运算表达式不会出现嵌套，即一定可以求出该表格的所有单元格的值。
要求算出值，并且以表格形式输出答案：
10 34 37 81 40 17 34 91 50 51 71 172
解题思路：
这道题其实可以直接用dfs搜索来完成，思路比较简单，关键是表格比较大，如何处理表格，如何建图比较关键。
我一开始采用二维的数组来存储表格，但是在搜索的过程中很难定位。其实可以把二维数组变为一维数组，然后一边输入数据，一边处理有表达式的单元格，同时将这些有表达式的单元格记录下来，以便于之后的dfs。另开一个sheet数组来记录单元格的数据，一个has数组来表示单元格是否已经为数值。在之后的搜索过程中能够省去不必要的查找。
代码：
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 100000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
vector<int> v[1100000];
int has[1100000];
int sheet[1100000];
int pd[10000];
int m, n;
int dfs(int u)
{
int i = 0, s = v[u].size(), sum = 0;
for (i = 0; i < s; i++)
{
if (!has[v[u][i]]) sum += dfs(v[u][i]);
else sum += sheet[v[u][i]];
}
has[u] = 1;
sheet[u] = sum;
return sum;
}
int main ()
{
int t, i, j;
cin>>t;
char str[1000];
while(t--)
{
mem(has, 0);
mem(sheet, 0);
cin>>n>>m;
int inx = 0;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
{
scanf("%s", str);
if (str[0] == ‘=‘)
{
int ii = i * n + j;
v[ii].clear();
int len = strlen(str), x = 0, y = 0, cas = 0;
str[len] = ‘+‘, str[len + 1] = ‘\0‘, len++;
for (int l = 1; l < len; l++)
{
if (isalpha(str[l])) x = x * 26 + str[l] - ‘A‘ + 1;
else if (isdigit(str[l])) y = y * 10 + str[l] - ‘0‘;
else
{
v[ii].push_back((y - 1) * n + x - 1);
x = 0, y = 0;
}
}
pd[inx++] = i * n + j;
}
else
{
sscanf(str, "%d", &sheet[i * n + j]);
has[i * n + j] = 1;
}
}
for (i = 0; i < inx; i++) if (!has[pd[i]])
dfs(pd[i]);
inx = 0;
for (i = 0; i < m; i++)
{
for (j = 0; j < n - 1; j++)
printf("%d ", sheet[inx++]);
printf("%d\n", sheet[inx++]);
}
}
return 0;
}