原题:https://uva.onlinejudge.org/external/2/215.pdf
有一个M x N的表格,每个单元格是个数字或者表达式。表达式由单元格编号和+ - 号组成
输出单元格的结果
思路:用dfs判断有向图环的问题
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <cstring>
#include <sstream> using namespace std;
const int MAXR = + , MAXC = + ;
string sheet[MAXR][MAXC];
int r, c;
bool hasCircle[MAXR][MAXC], f[MAXR][MAXC], ok; bool isNumber(int x, int y) {
string s = sheet[x][y];
int l = s.size();
if (isalpha(s[])) return false;
for (int i = ; i < l; i++) {
if (i != && !isdigit(s[i])) return false;
}
return true;
} void dfs(int x, int y) {
if (hasCircle[x][y] || isNumber(x, y)) return;
if (f[x][y]) {hasCircle[x][y] = ; return; }
f[x][y] = ;
string s = sheet[x][y];
char sign; int ans = , right, len = sheet[x][y].size(), i = ;
while (i < len) {
sign = '+';
if (s[i] == '-' || s[i] == '+') {
sign = s[i];
i++;
}
if (isalpha(s[i])) {
int nx = s[i] - 'A', ny = s[i + ] - '';
i += ;
dfs(nx, ny);
if (hasCircle[nx][ny]) {
hasCircle[x][y] = ;
return;
}
right = stoi(sheet[nx][ny]);
}
else {
int j = i + ;
while (j < len && isdigit(s[j])) j++;
right = stoi(s.substr(i, j - i));
i = j;
}
ans += right * ((sign == '+') ? : -);
}
stringstream ss; ss << ans;
ss >> sheet[x][y];
} int main() {
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
while (scanf("%d%d", &r, &c) == && r) {
memset(f, , sizeof(f));
memset(hasCircle, , sizeof(hasCircle));
ok = ;
for (int i = ; i < r; i++)
for (int j = ; j < c; j++)
cin >> sheet[i][j]; for (int i = ; i < r; i++)
for (int j = ; j < c; j++) {
if (!f[i][j])
dfs(i, j);
if (hasCircle[i][j]) ok = ;
}
if (!ok) {
for (int i = ; i < r; i++)
for (int j = ; j < c; j++)
if (hasCircle[i][j]) cout << char(i + 'A') << j << ": " << sheet[i][j] << endl;
}
else {
putchar(' ');
for (int i = ; i < c; i++) printf(" %d", i);
putchar('\n');
for (int i = ; i < r; i++) {
printf("%c", i + 'A');
for (int j = ; j < c; j++) {
for (int k = ; k < - sheet[i][j].size(); k++) putchar(' ');
cout << sheet[i][j];
}
putchar('\n');
}
}
putchar('\n');
} return ;
}