WOJ 110 Frame Stacking-所有拓撲排序序列

題目

題目連結

給出幾個互相交錯的框，輸出交疊的順序，根據題意，每個由字母組成的框（frame）的每一個邊都會至少有一個字母在交疊後的圖中，是以掃描一遍輸入圖就可以得到邊界。掃描其中一個框Y，如果邊上有其他字母X，則構造一條邊 X -> Y，表明框X在框Y之上。

算法

使用回溯法（深度優先搜尋），儲存每一個可能的排序。即如果目前存在兩個入度為0的節點A、B，先儲存A或先儲存B。

代碼

#include<iostream>
#include<vector>
#include<string>
#include <unordered_set>
#include <list>
#include <algorithm>

using namespace std;

struct Frame{
    int x1, x2, y1, y2;
    char letter;
    Frame(){
        this->letter = '.';
        x1 = y1 = 0x7fffffff;
        x2 = y2 = 0;
    }
};

void dfs(vector<string>& ans, list<char>& seq, vector<int>& count, unordered_set<char>& letters, const vector<vector<bool>>& graph) {
    if (seq.size() == letters.size()) {
        ans.emplace_back(seq.begin(), seq.end());
    } else {
        for (auto& c : letters) {
            if (count[c-'A'] == 0 && seq.end() == find(seq.begin(), seq.end(), c)) {
                for (auto& l : letters) {
                    if (graph[c-'A'][l-'A']) { // remove the edge  c -> l
                        count[l-'A']--;
                    }
                }
                // 注意題目要求從最下面的框開始輸出，是以頭插字母
                seq.insert(seq.begin(), c);
                dfs(ans, seq, count, letters, graph);
                // backtrack
                seq.pop_front();
                for (auto& l : letters) {
                    if (graph[c-'A'][l-'A']) {
                        count[l-'A']++;
                    }
                }
            }
        }
    }
}

int main() {
    int height, width;
    while (true) {
        cin >> height >> width;
        if (height==0 && width == 0) {
            break;
        }
        vector<string> board(height);
        unordered_set<char> Letters;

        for (int i = 0; i < height; ++i) {
            cin >> board[i];
            for_each(board[i].begin(), board[i].end(), [&Letters](char c){
                Letters.insert(c);
            });
        }
        Letters.erase('.');

        vector<Frame> frames(26);
		// 由于frame的每個邊都會至少有一個字母，掃描全圖确定邊界
        for (int i = 0; i < height; ++i) {
            for (int j = 0; j < width; ++j) {
                char curLetter = board[i][j];
                if (curLetter != '.') {
                    frames[curLetter-'A'].letter = curLetter;
                    frames[curLetter-'A'].x1 = min(frames[curLetter-'A'].x1, j);
                    frames[curLetter-'A'].x2 = max(frames[curLetter-'A'].x2, j);
                    frames[curLetter-'A'].y1 = min(frames[curLetter-'A'].y1, i);
                    frames[curLetter-'A'].y2 = max(frames[curLetter-'A'].y2, i);
                }
            }
        }

        vector<vector<bool>> graph(26, vector<bool>(26, false));
        char curLetter;
        for (auto& frame : frames) {
            if (frame.letter == '.') {
                continue;
            }
            // inspect up and down edges
            for (int i = frame.x1; i <= frame.x2; ++i) {
                curLetter = board[frame.y1][i];
                if (curLetter != frame.letter) {
                    graph[curLetter - 'A'][frame.letter - 'A'] = true; // 建構一條從 curLetter -> frame.letter 的邊
                }
                curLetter = board[frame.y2][i];
                if (curLetter != frame.letter) {
                    graph[curLetter - 'A'][frame.letter - 'A'] = true;
                }
            }
            // inspect left and right edges
            for (int i = frame.y1; i <= frame.y2; ++i) {
                curLetter = board[i][frame.x1];
                if (curLetter != frame.letter) {
                    graph[curLetter - 'A'][frame.letter - 'A'] = true;
                }
                curLetter = board[i][frame.x2];
                if (curLetter != frame.letter) {
                    graph[curLetter - 'A'][frame.letter - 'A'] = true;
                }
            }
        }
		// 入度記錄
        vector<int> count(26, 0);
        for (auto c : Letters) {
            for (int i = 0; i < 26; ++i) {
                if (graph[i][c - 'A']) {
                    count[c-'A']++;
                }
            }
        }
        list<char> seq;
        vector<string> answer;
        
        dfs(answer, seq, count, Letters, graph);
        
        // 按字典序輸出
        std::sort(answer.begin(), answer.end());
        for (auto& ans : answer) {
            cout << ans << endl;
        }
    }
    return 0;
}