首页 > 搜索 > DFS搜索 > HDU 1659 Spreadsheet-拓扑排序-[解题报告] C++
2013
12-21

HDU 1659 Spreadsheet-拓扑排序-[解题报告] C++

Spreadsheet

问题描述 :

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.

Figure: Naming of the top left cells

输入:

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, …, 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.

输出:

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.

样例输入:

1
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

 

题目类型: 搜索, 拓扑排序

 

分析与总结:

第一次看到这题是,我被吓到了,的的确确真的被吓到了! 倒不是说这题有多么多么地难,而是题目所给的数据范围: 表格有999行,18278列。 如果开一个

二维数组的话,那么就要开个1千8百万的数组, 在当前几乎所有的OJ上都是直接Runtime Error的。也就是说,这题就算写出程序来,也不可能AC的。

于是便暂时放下了。 后来,队友告诉我被题目给坑了, 实际上只需要开个1000*1000的数组就足矣了。 我倒!!

既然数据量这么少,那么就好办了。 这题只需要直接用递归搜索即可。

题目比较麻烦的是数据的转换,就是形如A3,B4, AB22这些的转换,字母相当于是26进制的数,表示的是列数, 数字的是表示行。

用拓扑排序做时,需要做一个转换, 把二维数组转换成一位数组。当然,除了搜索的解法,还可以用拓扑排序来解。

 

递归搜索解法:

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cctype>
#include<string>
#define MAXN 1010 
#define MARK -2147483645  //用来标记未得到结果的、是公式的格子

using namespace std;
int sheet[MAXN][MAXN];
int row, col;
string str; 
string fm[MAXN][MAXN]; // 保存公式


int dfs(int r,int c){
    if(sheet[r][c] != MARK) return sheet[r][c];
    if(sheet[r][c] == MARK){
        int m_row, m_col;
        char temp[MAXN]; 
	string str = fm[r][c];

        sheet[r][c] = 0;

        for(int i=1, pos=0; i<=str.size()+1; ++i){
            if(str[i]=='+' || i==str.size()){
                temp[pos] = '\0'; 
                m_row=0, m_col=0;
                int k;
                for(k=0; k<strlen(temp) && !isdigit(temp[k]); ++k){
                    m_col = m_col*26+temp[k]-'A'+1;
                    }
                for( ; k<strlen(temp); ++k){
                    m_row = m_row*10+temp[k]-'0'; 
                }
                pos = 0;
                sheet[r][c] += dfs(m_row, m_col);
            }
            else{
                temp[pos++] = str[i];
            }
        }
        return sheet[r][c];
    }
}


int main(){
#ifdef LOCAL
    freopen("input.txt","r",stdin);
#endif
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&col, &row);

        memset(sheet, 0, sizeof(sheet));

        int val;
        for(int i=1; i<=row; ++i){
            for(int j=1; j<=col; ++j){
 
                cin >> str;

                if(str[0]=='='){
                    sheet[i][j] = MARK;
                    fm[i][j] = str;
                }
                else{
                    val = atoi(str.c_str());
                    sheet[i][j] = val;   
                }
            }
        } 
        for(int i=1; i<=row; ++i){
            for(int j=1; j<=col; ++j) if(sheet[i][j]==MARK){
                dfs(i,j);
            }
        }  

        for(int i=1; i<=row; ++i){
            printf("%d",sheet[i][1]);
            for(int j=2; j<=col; ++j){
                printf(" %d",sheet[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/shuangde800/article/details/7726723