[C++知识库]算法竞赛入门经典 习题6-13

UVa215

Spreadsheet Calculator

计算并输出电子表格中每个单元格的值，如果出现循环引用，则输出无法求值的单元格。

这道题还是有一些实际意义的，解法就是深搜。

根据题目中的描述，表达式中只有单元格的引用、常量、加号和减号，所以在解析表达式时可以存储单元格索引以及求值过程中该单元格的倍数，至于常量可以直接计算。

题目中说单元格中要么就只有一个数字，要么就是以单元格索引开始的表达式，并且表达式没有前导空格，中间也没有空格，但是uDebug上的一些样例并不符合上述要求。

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;

struct Cell
{
    string index, expr;
    map<string, int> deps;
    int value = 0;
    bool evaluated = false;
    Cell() = default;
    Cell(size_t i, size_t j, const string& expr) : expr(expr)
    {
        index.push_back(static_cast<char>(i + 'A'));
        index.push_back(static_cast<char>(j + '0'));
        if (expr.front() == '-' || isdigit(expr.front())) {
            evaluated = true;
            value = stoi(expr);
        }
        else {
            evaluated = false;
            int times = 1;
            string item;
            string::const_iterator curr = expr.begin(), OperatorPosition;
            while (1) {
                OperatorPosition = find_if(curr, expr.end(), [](const char ch) { return ch == '+' || ch == '-'; });
                item.assign(curr, OperatorPosition);
                if (isdigit(*curr)) {
                    int constant = stoi(item);
                    if (times == 1) value += constant;
                    else value -= constant;
                }
                else {
                    deps[item] += times;
                }
                if (OperatorPosition != expr.end()) {
                    curr = OperatorPosition + 1;
                    if (*OperatorPosition == '+') times = 1;
                    else times = -1;
                }
                else break;
            }
        }
    }
};

class Solution
{
public:
    Solution(const vector<vector<Cell>> &input) : sheet(input), visited(sheet.size(), vector<bool>(sheet[0].size(), false))
    {
        for (size_t i = 0; i < sheet.size(); i++)
        {
            for (size_t j = 0; j < sheet[i].size(); j++)
            {
                if (!sheet[i][j].evaluated && !visited[i][j]) {
                    visited[i][j] = true;
                    if (!evaluate(sheet[i][j])) {
                        CircleReference.insert(make_pair(i, j));
                    }
                }
            }
        }
    }
    void print(ostream& os)
    {
        if (!CircleReference.empty()) {
            for (const pair<size_t, size_t> &RowCol : CircleReference)
            {
                os << sheet[RowCol.first][RowCol.second].index << ": " << sheet[RowCol.first][RowCol.second].expr << '\n';
            }
        }
        else {
            os << ' ';
            for (size_t col = 0; col < sheet[0].size(); col++)
            {
                os << setw(6) << setfill(' ') << col;
            }
            os << '\n';
            for (size_t row = 0; row < sheet.size(); row++)
            {
                os << static_cast<char>('A' + row);
                for (size_t col = 0; col < sheet[row].size(); col++)
                {
                    os << setw(6) << setfill(' ') << sheet[row][col].value;
                }
                os << '\n';
            }
        }
    }
private:
    vector<vector<Cell>> sheet;
    set<pair<size_t, size_t>> CircleReference;
    vector<vector<bool>> visited;
    bool evaluate(Cell &cell)
    {
        for (auto iter = cell.deps.begin(); iter != cell.deps.end(); iter++)
        {
            const string &DepIndex = iter->first;
            size_t DepRow = DepIndex[0] - 'A', DepCol = DepIndex[1] - '0';
            Cell& DepCell = sheet[DepRow][DepCol];
            if (DepCell.evaluated) {
                cell.value += iter->second * DepCell.value;
            }
            else if (!visited[DepRow][DepCol]) {
                visited[DepRow][DepCol] = true;
                if (evaluate(DepCell)) {
                    cell.value += iter->second * DepCell.value;
                }
                else {
                    CircleReference.insert(make_pair(DepRow, DepCol));
                    return false;
                }
            }
            else return false;
        }
        cell.evaluated = true;
        return true;
    }
};

int main()
{
    size_t row, col;
    while (cin >> row >> col) {
        if (row == 0 && col == 0) break;
        vector<vector<Cell>> sheet(row);
        string expr;
        for (size_t i = 0; i < row; i++)
        {
            for (size_t j = 0; j < col; j++)
            {
                cin >> expr;
                sheet[i].push_back(Cell(i, j, expr));
            }
        }
        Solution solution(sheet);
        solution.print(cout);
        cout << endl;
    }
}
/*
2 2
A1+B1
5
3
B0-A1
3 2
A0
5
C1
7
A1+B1
B0+A1
0 0
*/