POJ1420 HDU1659 UVA196 UVALive5606 Spreadsheet【DFS】

Spreadsheet
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 896 Accepted: 418

Description

In 1979, Dan Bricklin and Bob Frankston wrote VisiCalc, the first spreadsheet application. It became a huge success and, at that time, was the killer application for the Apple II computers. Today, spreadsheets are found on most desktop computers.

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

The first line of the input file contains the number of spreadsheets to follow. A spreadsheet starts with a line consisting of two integer numbers, separated by a space, giving the number of columns and rows. The following lines of the spreadsheet each contain a row. A row consists of the cells of that row, separated by a single space.

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

The output of your program should have the same format as the input, except that the number of spreadsheets and the number of columns and rows are not repeated. Furthermore, all formulas should be replaced by their value.

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

Southwestern European Regional Contest 1995

Regionals 1995 >> Europe - Southwestern

问题链接：POJ1420 HDU1659 UVA196 UVALive5606 Spreadsheet
问题简述：（略）
问题分析：
    繁琐的表格计算处理问题。
    表格的值如果以整数形式给定则可以直接计算赋值。如果表格中的某一项给的是表达式，其值则需要进行表达式求值得到。好在表达式中只有"+"运算，所以求值过程相对简单。本题的表达式计算，简单处理的话，使用迭代计算即可，也可以先进行拓扑排序后再行计算。本题解采用迭代计算。
    程序中表格列数太多时会出现MLE！！！需要注意存储限制。尤其是POJ，常量R和C都使用100就可以AC。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序如下：

/* POJ1420 HDU1659 UVA196 UVALive5606 Spreadsheet */

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>

using namespace std;

const int N = 26;
const int R = 999;
//const int C = N + N * N + N * N * N;
const int C = 1000;
int table[R + 1][C + 1];
vector<pair<int, int> > v[R][C + 1];
char s[100];

void init(char s[], int row, int col)
{
    if(isdigit(s[0]))
        table[row][col] = atoi(s);
    else {
        v[row][col].clear();

        int k = 0, row2, col2;
        while (s[k]) {
            k++;
            row2 = col2 = 0;
            while (isalpha(s[k]))
                col2 = col2 * N + s[k] - 'A' + 1, k++;
            while (isdigit(s[k]))
                row2 = row2 * 10 + s[k] - '0', k++;
            v[row][col].push_back(make_pair(row2, col2));
        }
    }
}

int dfs(int row, int col)
{
    if (table[row][col] != -1)
        return table[row][col];

    int res=0;
    for (int i = 0; i < (int)v[row][col].size(); i++)
        res += dfs(v[row][col][i].first, v[row][col][i].second);
    return res;
}

int main()
{
    int t, c, r;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &c, &r);

        memset(table, -1, sizeof(table));

        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= c; j++) {
                scanf("%s", s);
                init(s, i, j);
            }

        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= c; j++) {
                if (table[i][j] == -1)
                    table[i][j] = dfs(i, j);
                printf(j == c ? "%d\n" : "%d ", table[i][j]);
            }
    }

    return 0;
}