［UVA 196］Spreadsheet(DFS深検索＋配達)

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
", sheet[inx++]);
        }
    }
    return 0;
}