/*
http://acm.pku.edu.cn/JudgeOnline/problem?id=1128
DFS回溯实现拓扑排序 */ #include <iostream> #include <memory> #include <string> #include <algorithm> #define MAX_N 32 #define MAX_L 26 using namespace std; char mapv[MAX_N + 1][MAX_N + 1]; //记录输入 char letter[MAX_L + 1]; //记录输入中输出的字母c, C - 'A' + 1 bool graph[MAX_L + 1][MAX_L + 1]; //graph[i][j] = true, 表示i frame 排在 j frame的上面 int rowN, colN, lNum, resNum; //输入的行数，列数，lnum表述输入中出现的字母的类别数，resNum记录输出的结果数目 int pos[MAX_L + 1][4]; //记录各个字母上下左右的Index, 从1开始记录 bool v[MAX_L + 1]; //记录结果 struct node { string seq; node() { seq = ""; } }res[200]; //从0开始存 void init() { resNum = lNum = 0; memset(pos, 0, sizeof(pos)); memset(graph, 0, sizeof(graph)); } bool compare(const node n1, const node n2) { if(n1.seq <= n2.seq) return true; return false; } void topSort(int layer, string seqStr) { //排完了，每排一个字母，layer + 1， 直到排完所有的字母 if(layer > lNum) { //记录结果 res[resNum++].seq = seqStr; return; } int minCom = INT_MAX, s, k, curL, curCom; int minNum = 0; //向temp这类数据必须使用局部数据，应为没一层的temp必须不能受其他层影响， //一开把temp设成了全局的，这样进入下一层后，下一层可能会修改上面层的temp，从而产生错误结果 int temp[MAX_L + 1]; //寻找入度最小的点，这个点对应的frame应该是放在最上面的frame(可能不唯一，所以会产生多个结果) for(s = 0; s < lNum; s++) { //当前结点是上面已经处理过已经被抹去的点 if(letter[s] == '.') continue; curCom = 0; curL = letter[s] - 'A' + 1; for(k = 1; k <= MAX_L; k++) if(graph[k][curL]) curCom++; //找到更小入度的点 if(curCom < minCom) { minCom = curCom; minNum = 1; temp[minNum] = curL; //temp 从1开始存 } //和最小度数相等，则记录，并使minNum + 1 else if(curCom == minCom) { temp[++minNum] = curL; } } //回溯遍历所有的当前入度最小的点 seqStr = "." + seqStr; for(s = 1; s <= minNum; s++) { curL = temp[s]; //copyR和copyC也必须是局部数，原因和temp相同 bool copyR[MAX_L + 1], copyC[MAX_L + 1]; memset(copyR, 0, sizeof(copyR)); memset(copyC, 0, sizeof(copyC)); //保存当前节点对应的数据，并置位 for(k = 1; k <= MAX_L; k++) { copyR[k] = graph[curL][k]; copyC[k] = graph[k][curL]; graph[curL][k] = graph[k][curL] = false; } seqStr[0] = curL - 1 + 'A'; //已经处理过的节点要摸去 int tempPos; for(k = 0; k < lNum; k++) { if(letter[k] == curL - 1 + 'A') { tempPos = k; letter[k] = '.'; break; } } //dfs topSort(layer + 1, seqStr); //恢复相关数据 letter[tempPos] = curL - 1 + 'A'; for(k = 1; k <= MAX_L; k++) { graph[curL][k] = copyR[k]; graph[k][curL] = copyC[k]; } } } int main() { int i, j, k; char c, cc; while(cin>>rowN) { cin>>colN; //input process init(); for(i = 1; i <= rowN; i++) { for(j = 1; j <= colN; j++) { cin>>c; mapv[i][j] = c; if(c >= 'A' && c <= 'Z') { for(k = 0; k < lNum; k++) if(letter[k] == c) break; if(k >= lNum) letter[lNum++] = c; } } } ///寻找每个frame最上方和最下方的行号，已经最左边和最右边的列号 int s, p0, p1, p2, t, curL; //扫描行 for(i = 1; i <= rowN; i++) { //扫描任意列 for(j = 1; j <= colN; j++) { c = mapv[i][j]; cc = mapv[rowN - i + 1][j]; if(c >= 'A' && c <= 'Z') { if(pos[c - 'A' + 1][0] == 0) pos[c - 'A' + 1][0] = i; } if(cc >= 'A' && cc <= 'Z') { if(pos[cc - 'A' + 1][1] == 0) pos[cc - 'A' + 1][1] = rowN - i + 1; } } } //列扫描 for(i = 1; i <= colN; i++) { //扫描任意行 for(j = 1; j <= rowN; j++) { c = mapv[j][i]; cc = mapv[j][colN - i + 1]; if(c >= 'A' && c <= 'Z') { if(pos[c - 'A' + 1][2] == 0) pos[c - 'A' + 1][2] = i; } if(cc >= 'A' && cc <= 'Z') { if(pos[cc - 'A' + 1][3] == 0) pos[cc - 'A' + 1][3] = colN - i + 1; } } } ///顺次处理每个节点s,如果在s的四条边线中夹杂有其他节点t，那么表示 //t遮住了s, graph[t][s] 设置为true for(s = 0; s < lNum; s++) { curL = letter[s] - 'A' + 1; memset(v, 0, sizeof(v)); for(i = 0; i < 4; i++) { p0 = pos[curL][i]; int j = ((int(i / 2) + 1) * 2) % 4; p1 = pos[curL][j]; p2 = pos[curL][j + 1]; for(t = p1; t <= p2; t ++) { if(i <= 1) { if(mapv[p0][t] == letter[s]) continue; if(v[mapv[p0][t] - 'A' + 1]) continue; if(!(mapv[p0][t] >= 'A' && mapv[p0][t] <= 'Z')) continue; v[mapv[p0][t] - 'A' + 1] = true; graph[mapv[p0][t] - 'A' + 1][curL] = true; } else { if(mapv[t][p0] == letter[s]) continue; if(v[mapv[t][p0] - 'A' + 1]) continue; if(!(mapv[t][p0] >= 'A' && mapv[t][p0] <= 'Z')) continue; v[mapv[t][p0] - 'A' + 1] = true; graph[mapv[t][p0] - 'A' + 1][curL] = true; } } } } string str = ""; topSort(1, str); sort(res, res + resNum, compare); for(i = 0; i < resNum; i++) cout<<res[i].seq<<endl; / } return 0; }
