武汉专业做网站/百度推广代理商查询

题目大意：一个电子表格，输入所有位置的表达式或数字，输出电子表格每个位置的值。

解题思路：拓扑排序+dfs。将每个位置作为点，如果该位置为表达式，则将表达式包含的位置作为一种二元关系。入度为0（既数字或原表达式后已经求出值）则不操作，否则，进入dfs求出该位置的值。dfs中会进入该位置表达式中的位置从而求解。一个重要的地方是(因为我不看题目。。。看了题目的不用往下看)因为他是很多行、列的，行由数字代替很好理解。但是列用字母表示，当列大于26时，他的表示方式依旧是用字母，多个字母，例如:AA、A, AB, AC, ..., AZ, BA, ..., BZ, CA, ..., ZZ, AAA, AAB, ..., AAZ, ABA, ..., ABZ, ACA, ..., ZZZ。

ac代码：

#include <iostream>
#include <cstring>
using namespace std;
int n, r, c, topo[1000005], in[1000005], pre[1000005][100];
int len, temp, temp2;
char ch[1005];
bool dfs(int u)
{int s=0;for (int i=0; i<in[u]; i++){if (in[pre[u][i]] && !dfs(pre[u][i]))return false;s += topo[pre[u][i]];}topo[u] = s;in[u] = 0;
return true;
}bool toposort()
{for (int i=0; i<c*r; i++)if (in[i] && !dfs(i))return false;return true;
}
int main(){scanf("%d", &n);while (n--){scanf("%d%d", &c, &r);memset(in, 0, sizeof(in));memset(pre, 0, sizeof(pre));memset(topo, 0, sizeof(topo));for (int i=0; i<r*c; i++){scanf("%s", ch);	if (ch[0] == '='){len = strlen(ch);for (int k=1; k<len; k++){if (isalpha(ch[k])){						temp = temp2 = 0;temp = ch[k++] - 'A' + 1;while (isalpha(ch[k]))temp = temp * 26 + ch[k++] - 'A' + 1;while (ch[k] >= '0' && ch[k] <= '9' && k<len)temp2 = temp2 * 10 + (ch[k++] - '0');pre[i][in[i]++] = (temp2-1) * c + temp - 1;}}}elsesscanf(ch, "%d", &topo[i]);			}toposort();  for (int i=0; i<r; i++)for (int j=0; j<c; j++)printf(j==c-1?"%d\n":"%d ", topo[i*c+j]);}
return 0;
}