ACM/ICPC 之 拓扑排序+DFS(POJ1128(ZOJ1083)-POJ1270)

两道经典的同类型拓扑排序+DFS问题，第二题较第一题简单，其中的难点在于字典序输出+建立单向无环图，另外理解题意是最难的难点，没有之一...

---

POJ1128(ZOJ1083)-Frame Stacking

　　题意：每个图片由同一字母组成的边框表示，每个图片的字母都不同；

　　　　　在一个最多30*30的区域放置这些图片，问底层向顶层叠加的图片次序，多选时按字典序输出

　　　　　注:每个图片的四边都会有字符显示，其中顶点显示两边。

　　题解：题意的理解是难点，题目对图片的范围确定说得有点含糊不清，博主一开始就被出现的五张图片的样例迷惑，理解重心放错了。题目最需要理解的是下方的三句话。

　　　　　第一句和数据范围就确定了图片尺寸；

　　　　　第二句话提示读者应该考虑记录对角线上的两个顶点，以此记录该图片的位置和尺寸；

　　　　　第三句话确定了图片的数量及可以标明该图片的key值（字母）

　　　　　最后要注意Input中有多组样例，而Ouput中的多组次序需要按照字典序输出。

　　　　　理清题意后：接下来的工作就是先用两个顶点确立图片的位置和尺寸；

　　　　　　　　　　　接着利用各图片的位置和尺寸确定覆盖关系建立单向无环图；

　　　　　　　　　　　最后利用DFS的回溯完成字典序的拓扑排序即可。

 //叠图片-拓扑排序+DFS

 //每个图片由同一字母组成的边框表示，每个图片的字母都不同

 //在一个最多30*30的区域放置这些图片，问底层向顶层叠加的图片次序，多选时按字典序输出

 //注:每个图片的四边都至少会有一个字符显示

 //Time:0Ms    Memory:180K

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<algorithm>

 using namespace std;

 #define MAXN 31    //地图长宽

 #define MAXL 26    //字母

 struct Coordinate{

     int x, y;

 }lt[MAXL], rb[MAXL];    //left_top - right_bottom

 struct Letter {

     vector<int> covered;

     int in;            //in_degree

     bool exist;

 }let[MAXL];

 int row, col;

 int total;    //字母个数

 char ans[MAXL+];

 char board[MAXN][MAXN];

 void dfs(int len)

 {

     if (len == total)

     {

         ans[len] = '\0';

         printf("%s\n", ans);

         return;

     }

     for (int i = ; i < MAXL; i++)

     {

         if (!let[i].exist) continue;

         if (let[i].in == )

         {

             ans[len] = i + 'A';

             let[i].in--;

             for (int j = ; j < let[i].covered.size(); j++)

                 let[let[i].covered[j]].in--;

             dfs(len + );

             for (int j = ; j < let[i].covered.size(); j++)

                 let[let[i].covered[j]].in++;

             let[i].in++;

         }

     }

 }

 int main()

 {

     while (scanf("%d%d", &row, &col) != EOF)

     {

         total = ;

         memset(let, , sizeof(let));

         memset(lt, 0x3f, sizeof(lt));

         memset(rb, -, sizeof(rb));

         //Input and Init

         for (int i = ; i < row; i++)

         {

             scanf("%s", board[i]);

             for (int j = ; j < col; j++)

             {

                 if (board[i][j] == '.') continue;

                 int t = board[i][j] - 'A';

                 if (!let[t].exist)

                     let[t].exist = ++total;

                 lt[t].x = min(lt[t].x, i);

                 lt[t].y = min(lt[t].y, j);

                 rb[t].x = max(rb[t].x, i);

                 rb[t].y = max(rb[t].y, j);

             }

         }

         //get_Map

         for (int k = ; k < MAXL; k++)

         {

             if (!let[k].exist) continue;

             for (int i = lt[k].x; i <= rb[k].x; i++)

                 for (int j = lt[k].y; j <= rb[k].y; j++)

                 {

                     if (i > lt[k].x && i < rb[k].x && j == lt[k].y + )

                         j = rb[k].y;

                     int cur = board[i][j] - 'A';

                     if (cur == k) continue;

                     let[k].covered.push_back(cur);

                     let[cur].in++;

                 }

         }

         //Topology and Output

         dfs();

     }

     return ;

 }

---

POJ1270-Following Orders

　　本题相当于POJ1128的同类改编题型，相比1128简单。

　　题意：给定第一行的小写字母，第二行每两个字母描述其约束关系，例如x y 即 x<y，求可以得到的所有有序序列。

　　题解：这个题目的Input也是让人很醉啊，为了循环接受一行字符，需要使用读取到'\n'才停止的函数。

　　　　　可以实现的类似的函数有gets，fgets，sscanf；getchar（循环接受单字符）；string的getline和cin的getline及get等等

　　　　　为了方便书写和之后的字符处理，折中选取了cin的getline函数

　　　　　　　　　cin.getline(str,MAX,'\n')：读入最多MAX大的字符串存入str，直到'\n'停止(可以不需要第三个参数)

　　　　　之后的处理和POJ1128的题解一致，依旧是构图+拓扑排序+DFS，不再累述。

 //有序序列-拓扑排序+DFS

 //一个难点在于输入，如果使用C语言的gets或者fgets总觉得不好处理

 //    于是利用了cin的getline函数，会将'\n'转换成'\0',利于处理

 //另一个难点在于字典序输出，需要利用到DFS的回溯

 //其余的操作与拓扑排序相同

 //Time:0Ms    Memory:208K

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<algorithm>

 using namespace std;

 #define MAX 50

 struct Letter {

     vector<int> bigger;

     int in;        //in_degree

     bool exist;

 }let[];

 int total;

 char ans[MAX];

 void dfs(int len)

 {

     if (len == total)

     {

         ans[len] = '\0';

         printf("%s\n", ans);

         return;

     }

     for (int i = ; i < ; i++)

     {

         if (!let[i].exist || let[i].in) continue;

         let[i].in--;

         for (unsigned j = ; j < let[i].bigger.size(); j++)

             let[let[i].bigger[j]].in--;

         ans[len] = i + 'a';

         dfs(len + );

         for (unsigned j = ; j < let[i].bigger.size(); j++)

             let[let[i].bigger[j]].in++;

         let[i].in++;

     }

 }

 int main()

 {

     char str[MAX];

     while (cin.getline(str, MAX, '\n'))

     {

         total = ;

         memset(let, , sizeof(let));

         int len = strlen(str);

         for (int i = ; i < len; i += )

             if(!let[str[i] - 'a'].exist)

                 let[str[i] - 'a'].exist = ++total;

         cin.getline(str, MAX, '\n');

         len = strlen(str);

         for (int i = ; i < len; i += )

         {

             int small = str[i] - 'a';

             int big = str[i + ] - 'a';

             let[small].bigger.push_back(big);

             let[big].in++;

         }

         dfs();

         printf("\n");

     }

     return ;

 }

ACM/ICPC 之 拓扑排序+DFS(POJ1128(ZOJ1083)-POJ1270)的相关教程结束。