uva 215 Spreadsheet Calculator

A spreadsheet is a rectangular array of cells. Cells contain data or expressions that can be evaluated toobtain data. A “simple” spreadsheet is one in which data are integers and expressions are mixed sumsand differences of integers and cell references. For any expression, if each cell that is referenced containsan integer, then the expression can be replaced by the integer to which the expression evaluates. Youare to write a program which evaluates simple spreadsheets.InputInput consists of a sequence of simple spreadsheets. Each spreadsheet begins with a line specifying thenumber of rows and the number of columns. No spreadsheet contains more than 20 rows or 10 columns.Rows are labeled by capital letters A through T. Columns are labeled by decimal digits 0 through 9.Therefore, the cell in the first row and first column is referenced as A0; the cell in the twentieth rowand fifth column is referenced as T4.Following the specification of the number of rows and columns is one line of data for each cell,presented in row-major order. (That is, all cells for the first row come first, followed by all cells for thesecond row, etc.)Each cell initially contains a signed integer value or an expression involving unsigned integer constants,cell references, and the operators + (addition) and - (subtraction).If a cell initially contains a signed integer, the corresponding input line will begin with an optionalminus sign followed by one or more decimal digits.If a cell initially contains an expression, its input line will contain one or more cell references orunsigned integer constants separated from each other by + and - signs. Such a line must begin witha cell reference. No expression contains more than 75 characters. No line of input contains leadingblanks. No expression contains any embedded blanks. However, any line may contain trailing blanks.The end of the sequence of spreadsheets is marked by a line specifying 0 rows and 0 columns.OutputFor each spreadsheet in the input, you are to determine the value of each expression and displaythe resulting spreadsheet as a rectangular array of numbers with the rows and columns appropriatelylabeled. In each display, all numbers for a column must appear right-justified and aligned with thecolumn label.Operators are evaluated left to right in each expression; values in cells are always less than 10000in absolute value. Since expressions may reference cells that themselves contain expressions, the orderin which cells are evaluated is dependent on the expressions themselves.If one or more cells in a spreadsheet contain expressions with circular references, then the outputfor that spreadsheet should contain only a list of the unevaluated cells in row-major order, one per line,with each line containing the cell label, a colon, a blank, and the cell’s original expression.A blank line should appear following the output for each spreadsheet.Sample Input2 2A1+B153B0-A13 2A05C17A1+B1B0+A10 0Sample Output0 1A 3 5B 3 -2A0: A0B0: C1C1: B0+A1

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;
const int mx=123456;
typedef pair<int,int > P;
int n,m,mp[22][22],extra[22][22];
char ss[220][1000];
vector<P> g[300];
bool used[222];
void init()
{
     for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)mp[i][j]=mx;
     memset(used,0,sizeof(used));
     memset(extra,0,sizeof(extra));
     for(int i=0;i<210;i++) g[i].clear();
}
void add_edge(int u,int v,int fu)
{
    g[u].push_back(P(v,fu) );
}
void jiexi(char *s,int x,int y)
{
    if(s[0]>='0'&&s[0]<='9'||s[0]=='-'||s[0]=='+' ) {sscanf(s,"%d",&mp[x][y]);return ;}
    int sum=0;
    for(int i=0;s[i];i++)
    {
        if(s[i]>='A'&&s[i]<='T'||s[i]=='+'||s[i]=='-')
        {
            int fu=1,nx,ny;
            if(s[i]=='-')fu=-1,i++;
            else if(s[i]=='+')i++;
            if(s[i]>='0'&&s[i]<='9')
            {
                int num=0;
                while(s[i]>='0'&&s[i]<='9') num=num*10+s[i]-'0',i++;
                i--;
                sum+=num*fu;
                continue;
            }
            nx=s[i]-'A',i++;
            ny=s[i]-'0';
            add_edge(x*m+y,(nx*m+ny),fu);
        }
    }
    extra[x][y]=sum;
}
int dfs(int u)
{
    used[u]=true;
    if(mp[u/m][u%m]!=mx) return mp[u/m][u%m];
    int sum=0;
    for(int i=0;i<g[u].size();i++)
    {
        P v=g[u][i];
        if(!used[v.first])
        {
            int res=dfs(v.first);
            if(res==mx) return mx;
            sum+=res*v.second;
        }
        else
        {
            int k=v.first;
            if(mp[k/m][k%m]==mx) return mx;
            else sum+=mp[k/m][k%m]*v.second;
        }
    }
    return mp[u/m][u%m]=sum+extra[u/m][u%m];
}
void print(int x,int y)
{
    int num=x*m+y;printf("%c%c: ",x+'A',y+'0');
    printf("%s\n",ss[num]);
}
int main()
{
    int T=0;
    while(scanf("%d%d",&n,&m),n||m)
    {
       init();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {scanf("%s",ss[i*m+j]);jiexi(ss[i*m+j],i,j);}
      //  if(T)printf("\n");T++;
        int flag=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
        {
            dfs(i*m+j);
            if(mp[i][j]==mx)flag=1;
        }
        if(flag)
        {
            for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
            {
                if(mp[i][j]==mx) print(i,j);
            }
        }
        else
        {
            printf(" ");
            for(int i=0;i<m;i++)printf("%6d",i);printf("\n");
            for(int i=0;i<n;i++)
            {
                printf("%c",i+'A');
                for(int j=0;j<m;j++)printf("%6d",mp[i][j]);printf("\n");
            }
        }
        printf("\n");
    }
    return 0;
}
           

有個細節問題，最後一個輸出塊要輸出一個空行，否則會判WA

此題主要是一個dfs，不過有很多細節需要注意