原题: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 ;
}

最新文章

  1. PL/0编译器实践---后记
  2. redis学习教程地址
  3. ionic 的下拉刷新 与 上拉加载
  4. JSP弹出窗口和模式对话框
  5. (转)Jquery最实用的实例及源码(http://www.cnblogs.com/kingfly/archive/2012/12/05/2802539.html)
  6. IOS表情存入MYSQL数据库失败
  7. 详解Bootstrap表单组件
  8. 设置SVN hooks实现自动发布
  9. poj 3641 Pseudoprime numbers Miller_Rabin测素裸题
  10. JavaScript 兼容处理IE67之 !&quot;a&quot;[0]
  11. how to get file from classpath using jboss7.x.1 --reference
  12. vsftpd配置---------------------之chroot_local_user和chroot_list_enable含义
  13. Delphi 取外网IP
  14. 后台生成textbox并设置多行属性,自动换行
  15. POJ1077&amp;&amp;HDU1043(八数码,IDA*+曼哈顿距离)
  16. Linux常用网络命令整理
  17. CSS引用样式
  18. Linux如何查找某个时间点后生成的空文件
  19. 【json】与【枚举】的序列化和反序列化
  20. 微信支付-H5网页支付开通流程

热门文章

  1. dedecms调用所有顶级栏目最新文章的实现方法
  2. Ext checkbox
  3. Access数据库数据转换Table.Json
  4. asp.net用Zxing库实现条形码输出的具体实现
  5. android 06
  6. mysql操作1
  7. Oracle的卸载与安装
  8. Excel报表
  9. python numpy 使用笔记 矩阵操作
  10. iOS开发网络篇—JSON数据的解析