算法入门经典2 第6章例题

【序】

                           第6章一共有22个例题，这些例题大多十分经典，在教材和题解的帮助下，已经全部通过了书上的例题。现在就把我做题过程总结一下。

【正文】

                         题目传送门：点击打开链接

          由于这些题都在书上有详细讲解，然后题意也有中文翻译，我就不写题意了，可以翻看紫书，了解题意。

【6-1】 模拟并行程序处理。STL队列 双端队列 的应用  用双端队列维护即将执行的程序  再用个队列维护等待变量释放的程序   用lock表示变量锁定状态先将所有程序依次放到执行队列中  每次取出队首程序运行不超过lim时间  未运行完又放到执行队列队尾 。遇到lock时  若当前锁定状态为false就将锁定状态变为true  否则将当前程序放到等待队列队尾并结束运行 ，遇到unlock时  若等待队列有程序  就将等待队列队首程序放到执行队列队首，遇到end时 退出当前执行(不再进队尾)。

bool lock;
deque <int> q1;
queue <int> q2; // q1代表等待队列，q2代表阻止队列
vector <string> v[maxn];
int Q, t[maxn], var[maxn], cnt[maxn];

void operate(int i)
{
    int x;
    int time = Q;
    string cur;
    while(time > 0)
    {
        cur = v[i][cnt[i]];
        if(cur[2] == '=')
        {
            time -= t[0];
            x = cur[4] - '0';
            if(cur.size() == 6){
                x = x * 10 + (cur[5] - '0');
            }
            var[cur[0] - 'a'] = x;
        }
        else if(cur[2] == 'i'){
            time -= t[1];
            printf("%d: %d\n", i, var[cur[6]-'a']);
        }
        else if(cur[2] == 'c'){
            time -= t[2];
            if(lock){
                q2.push(i);
                return ;
            }
            else{
                lock = 1;
            }
        }
        else if(cur[2] == 'l'){
            time -= t[3];
            lock = 0;
            if(!q2.empty()){
                x = q2.front(); q2.pop();
                q1.push_front(x);
            }
        }
        else{
            return ;
        }
        ++cnt[i];
    }
    q1.push_back(i);
}

int main()
{
    int T, n;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 0; i < 5; i++) scanf("%d", &t[i]);
        scanf("%d", &Q);
        memset(var, 0, sizeof(var));
        memset(cnt, 0, sizeof(cnt));
        while(!q1.empty()) q1.pop_back();
        while(!q2.empty()) q2.pop();
        string input;
        for(int i = 1; i <= n; i++){
            v[i].clear();
            while(getline(cin, input)){
                if(input == "") continue;
                //if(input == "end") break;
                v[i].push_back(input);
                if(v[i].back() == "end") break;
            }
            q1.push_back(i);
        }
        while(q1.size()){
            int u = q1.front(); q1.pop_front();
            operate(u);
        }
        if(T){
            printf("\n");
        }
    }
    return 0;
}

int n, a[maxn];

int main()
{
    while(cin>>n && n)
    {
        //while(!s.empty()) s.pop();
        while(cin>>a[1] && a[1])
        {
            stack <int> s;
            for(int i = 2; i <= n; i++) cin>>a[i];
            int l = 1, r = 1, ok = 1;
            while(r <= n)
            {
                if(l == a[r])
                {
                    l++, r++;
                }
                else if(!s.empty() && s.top() == a[r])
                {
                    s.pop();
                    r++;
                }
                else if(l <= n) s.push(l++);
                else
                {
                    ok = 0;
                    break;
                }
            }
            cout<<(ok ? "Yes" : "No")<<endl;
        }
        cout<<endl;
    }
    return 0;
}

【6-3】给出n个矩阵的维度和一些矩形链乘的表达式，要输出乘法次数。本题就是解析表达式，本题的表达很简单，可以用栈来完成：遇到字母时入栈，遇到右括号出栈并计算，然后结果入栈。AC代码见书上142页。

【6-4】单链表的简单应用。每输入一个字符就把它存起来，设输入的字符串是s[1-n]则可以用nxt【i】表示当前显示屏中s[i]右边的字符编号（即在s中的下标）。为了方便起见，假设字符串前面还有一个虚拟的s[0]，nxt【0】可以表示显示屏中最左的字符再用一个变量cur表示光标的位置：即当前光标位于s[cur]的右边。cur = 0说明光标位于虚拟字符 s[0]的右边，即是显示频的最左边，为了移动光标，还需要用一个last表示显示频的最后一个字符是s[last]。如果对这个过程不是很理解，可以在纸上模拟一下，做和链表相关的题，在纸上模拟一下还是很有必要的。

const int maxn = 100000 + 5;
int nex[maxn], cur, last; // 光标在cur的后面
char s[maxn];

int main()
{
    while(scanf("%s", s + 1) != EOF)
    {
        int n = strlen(s + 1);
        last = cur = 0;
        nex[0] = 0;
        for(int i = 1; i <= n; i++){
            char ch = s[i];
            if(ch == '[') cur = 0;
            else if(ch == ']') cur = last;
            else{
                nex[i] = nex[cur];
                nex[cur] = i;
                if(cur == last) last = i; //更新最后一个字符编号
                cur = i;
            }
        }
        for(int i = nex[0]; i != 0; i = nex[i]){
            printf("%c", s[i]);
        }
        printf("\n");
    }
    return 0;
}

int Left[maxn], Right[maxn];
void Link(int L, int R){ //双链表连接方式
    Right[L] = R; Left[R] = L;
}

const int maxn = 100010;
int Left[maxn], Right[maxn];
void Link(int L, int R){ //双链表连接方式
    Right[L] = R; Left[R] = L;
}
int inv;
int main()
{
    int n, m, ks = 0;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        //预处理双链表连接
        for(int i = 1; i <= n; i++){
            Left[i] = i - 1;
            Right[i] = (i + 1) % (n + 1);
        }
        Right[0] = 1; Left[0] = n;
        //处理查询
        int op, X, Y, inv = 0;
        while(m--)
        {
            scanf("%d", &op);
            if(op == 4) inv ^= 1;
            else{
                scanf("%d%d", &X, &Y);
                if(op == 3 && Right[Y] == X) swap(X, Y);
                if(op != 3 && inv) op = 3 - op;
                if(op == 1 && X == Left[Y]) continue;
                if(op == 2 && X == Right[Y]) continue;
                int LX = Left[X], RX = Right[X];
                int LY = Left[Y], RY = Right[Y];
                if(op == 1){
                    Link(LX, RX);
                    Link(LY, X);
                    Link(X, Y);
                }
                else if(op == 2){
                    Link(LX, RX);
                    Link(Y, X);
                    Link(X, RY);
                }
                else if(op == 3){
                    if(Right[X] == Y){
                        Link(LX, Y);
                        Link(Y, X);
                        Link(X, RY);
                    }
                    else{
                        Link(LX, Y);
                        Link(Y, RX);
                        Link(LY, X);
                        Link(X, RY);
                    }
                }
            }
        }
        int b = 0;
        long long ans = 0;
        for(int i = 1; i <= n; i++){
            b = Right[b];
            if(i % 2 == 1) ans += b;
        }
        if(inv && n % 2 == 0){
            ans = (long long) n * (n + 1) / 2 - ans;
        }
        printf("Case %d: %lld\n", ++ks, ans);
    }
    return 0;
}

每个小球都会落在根结点上，因此前两个小球必然是一个在左子树，一个在右子树。所以只需要看小球编号的奇偶性，就能知道它最终在哪棵子树中。对于那些落入根结点左子树的小球来说，只需要知道该小球是第几个落在根的左子树里的，就可以知道它下一步是往左还是往右了。依次类推，直到小球落到叶子上。

如果使用题目中给出的编号I，则当I是奇数时，它是往左走的第(I+1)/2个小球；当I是偶数时，它是往右走的第I/2个小球。这样，可以直接模拟最后一个小球的路线：

int k = 1;
        for(int i = 0; i < D - 1; i++){
            if(I % 2){
                k = k * 2;
                I = (I + 1) / 2;
            }
            else{
                k = k * 2 + 1;
                I = I / 2;
            }
        }
        printf("%d\n", k);

bool failed;

struct Node{
    bool have_value;
    int v;
    Node *left, *right;
    Node():have_value(false), left(NULL), right(NULL){}
};

Node *root;

Node* newnode(){return new Node();}

void addnode(int v, char *s)
{
    int n = strlen(s);
    Node *u = root;
    for(int i = 0; i < n; i++){
        if(s[i] == 'L'){
            if(u->left == NULL) u->left = newnode();
            u = u->left;
        }
        else if(s[i] == 'R'){
            if(u->right == NULL) u->right = newnode();
            u = u->right;
        }
    }
    if(u->have_value) failed = true;
    u->v = v;
    u->have_value = true;
}

void remove_tree(Node *u)
{
    if(u == NULL) return;
    remove_tree(u->left);
    remove_tree(u->right);
    delete u;
}

char s[maxn];
bool read_input(){
    failed = false;
    remove_tree(root);
    root = newnode();
    for(;;){
        if(scanf("%s", s) != 1) return false;
        if(!strcmp(s, "()")) break;
        int v;
        sscanf(&s[1], "%d", &v);
        addnode(v, strchr(s, ',') + 1);
    }
    return true;
}

bool bfs(vector <int> &ans)
{
    queue <Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node *u = q.front(); q.pop();
        if(!u->have_value) return false;
        ans.push_back(u->v);
        if(u->left != NULL) q.push(u->left);
        if(u->right != NULL) q.push(u->right);
    }
    return true;
}

int main()
{
    vector <int> ans;
    while(read_input()){
        if(!bfs(ans)){
            failed = 1;
        }
        if(failed){
            printf("not complete\n");
        }
        else{
            for(int i = 0; i < ans.size(); i++){
                printf("%d%c",ans[i],i==(int)(ans.size() - 1) ? '\n' : ' ');
            }
        }
    }
    return 0;
}

【6-8】 后序遍历的最后一个字符就是根，因此只需要在中序遍历里面找到它，就知道左右子树的中序和后序遍历了。这样可以先把二叉树构造出来，然后在执行一次递归遍历找到最优解。

const int maxv = 10010;

int in[maxv], post[maxv], lc[maxv], rc[maxv];
int n;
bool input(int *a){
    string line;
    if(!getline(cin, line)) return false;
    stringstream ss(line);
    n = 0;
    int x;
    while(ss >> x) a[n++] = x;
    return n > 0;
}

int build(int L1, int R1, int L2, int R2){
    if(L1 > R1) return 0;
    int root = post[R2];
    int p = L1;
    while(in[p] != root) p++;
    int cnt = p - L1;
    lc[root] = build(L1, p-1, L2, L2 + cnt - 1);
    rc[root] = build(p + 1, R1, L2 + cnt, R2 - 1);
    return root;
}

int best, best_sum;

void dfs(int u, int sum)
{
    sum += u;
    if(!lc[u] && !rc[u]){
        if(sum < best_sum || (sum == best_sum && u < best)){
            best = u;
            best_sum = sum;
        }
    }
    if(lc[u]) dfs(lc[u], sum);
    if(rc[u]) dfs(rc[u], sum);
}

int main()
{
    while(input(in)){
        input(post);
        build(0, n - 1, 0, n - 1);
        best_sum = 1e9;
        dfs(post[n-1], 0);
        printf("%d\n", best);
    }
    return 0;
}

【6-9】这道题目的输入就采取了递归定义的方式，因此编写一个递归的过程输入很自然。然后紫书上提供了一种很惊艳的做法，十分简便。使用引用传值，值得学习。

//代码功能为，输入一个子天平，返回天平是否平衡，参数W修改为天平的总重量
bool solve(int &W){
    int W1, D1, W2, D2;
    bool b1 = true, b2 = true;
    cin >> W1 >> D1 >> W2 >> D2;
    if(!W1) b1 = solve(W1);
    if(!W2) b2 = solve(W2);
    W = W1 + W2;
    return b1 && b2 && (W1 * D1 == W2 * D2);
}

int sum[maxn*3];
void build(int p)
{
    int v; cin>>v;
    if(v == -1) return;
    sum[p] += v;
    build(p - 1);
    build(p + 1);
}

bool input()
{
    int v; cin>>v;
    if(v == -1) return false;
    memset(sum, 0, sizeof(sum));
    int pos = maxn / 2;
    sum[pos] = v;
    build(pos - 1);
    build(pos + 1);
}
int main()
{
    int ks = 0;
    while(input())
    {
        int p = 0;
        while(sum[p] == 0) p++;
        printf("Case %d:\n", ++ks);
        printf("%d", sum[p++]);
        while(sum[p] != 0) printf(" %d", sum[p++]);
        printf("\n\n");
    }
    return 0;
}

const int len = 32;
char s[maxn];
int buf[len][len], cnt;

void draw(const char *s, int &p, int r, int c, int w)
{
    char ch = s[p++];
    if(ch == 'p'){
        draw(s, p, r, c + w / 2, w / 2); //1
        draw(s, p, r, c, w / 2); //2
        draw(s, p, r + w / 2, c, w / 2); //3
        draw(s, p, r + w / 2, c + w / 2, w / 2);
    }
    else if(ch == 'f'){
        for(int i = r; i < r + w; i++){
            for(int j = c; j < c + w; j++){
                if(buf[i][j] == 0){
                    buf[i][j] = 1;
                    cnt++;
                }
            }
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        memset(buf, 0, sizeof(buf));
        cnt = 0;
        for(int i = 0; i < 2; i++){
            scanf("%s", s);
            int p = 0;
            draw(s, p, 0, 0, len);
        }
        printf("There are %d black pixels.\n", cnt);
    }
    return 0;
}

char pic[maxn][maxn];
int m, n, idx[maxn][maxn]; //联通分量编号

void dfs(int r, int c, int id)
{
    if(r < 0 || r >= m || c < 0 || c >= n) return;
    if(idx[r][c] > 0 || pic[r][c] != '@') return;
    idx[r][c] = id;
    for(int dr = -1; dr <= 1; dr++)
        for(int dc = -1; dc <= 1; dc++)
            if(dr != 0 || dc != 0) dfs(r + dr, c + dc, id);
}

int main()
{
    while(scanf("%d%d", &m, &n) && m && n)
    {
        for(int i = 0; i < m; i++) scanf("%s", pic[i]);
        memset(idx, 0, sizeof(idx));
        int cnt = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(idx[i][j] == 0 && pic[i][j] == '@') dfs(i, j, ++cnt);
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
string code1[16] = {"0000", "0001", "0010", "0011",
                    "0100", "0101", "0110", "0111",
                   "1000", "1001", "1010", "1011",
                   "1100", "1101", "1110", "1111"};
char code2[8] = {'W', 'A', 'K', 'J', 'S', 'D'};
map <char, int> mp;
char maze[256][256];
int H, W, ks, cnt;

bool check(int x, int y)
{
    if(x >= 0 && x <= H + 1 && y >= 0 && y <= W + 1){
        return true;
    }
    else{
        return false;
    }
}

void dfs1(int r, int c)
{
    if(!check(r, c) || maze[r][c] != '0') return;
    maze[r][c] = '@';
    for(int i = 0; i < 4; i++){
        int dx = r + dir[i][0];
        int dy = c + dir[i][1];
        dfs1(dx, dy);
    }
}

void dfs2(int r, int c)
{
    if(!check(r, c) || maze[r][c] != '1') return;
    maze[r][c] = '@';
    for(int i = 0; i < 4; i++){
        int dx = r + dir[i][0];
        int dy = c + dir[i][1];
        if(maze[dx][dy] == '0'){
            ++cnt;
            dfs1(dx, dy);
        }
        else{
            dfs2(dx, dy);
        }
    }
}

int main()
{
    while(scanf("%d%d", &H, &W) != EOF)
    {
        if(H == 0 && W == 0) break;
        W = W * 4;
        memset(maze, '0', sizeof(maze));
        mp.clear();
        for(int i = 1; i <= H; i++){
            string line, tmp;
            cin >> line;
            for(auto i : line) tmp += code1[i >= 'a' ? (i - 'a' + 10) : (i - '0')];
            memcpy(maze[i] + 1, tmp.c_str(), W);
        }
//        for(int i = 1; i <= H; i++){
//            for(int j = 1; j <= W; j++){
//                printf("%c", maze[i][j]);
//            }
//            printf("\n");
//        }
//        printf("***************************************\n");
        dfs1(0, 0);
//        for(int i = 1; i <= H; i++){
//            for(int j = 1; j <= W; j++){
//                printf("%c", maze[i][j]);
//            }
//            printf("\n");
//        }
//        printf("***************************************\n");
        for(int i = 1; i <= H; i++){
            for(int j = 1; j <= W; j++){
                if(maze[i][j] != '1') continue;
                cnt = 0;
                dfs2(i, j);
                mp[code2[cnt]]++;
            }
        }
        printf("Case %d: ", ++ks);
        for(auto it : mp)
        {
            while(it.second--){
                printf("%c", it.first);
            }
        }
        printf("\n");
    }
    return 0;
}

const char *dirs = "NESW";
const char *turns = "FLR";

int dir_id(char c)
{
    return strchr(dirs, c) - dirs;
}

int turn_id(char c)
{
    return strchr(turns, c) - turns;
}

bool check(int x, int y)
{
    if(x >= 1 && x <= 9 && y >= 1 && y <= 9) return true;
    else return false;
}

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};

Node walk(const Node &u, int turn){
    int dir = u.dir;
    if(turn == 1) dir = (dir + 3) % 4; //逆时针
    if(turn == 2) dir = (dir + 1) % 4; //顺时针
    return Node(u.r + dr[dir], u.c + dc[dir], dir);
}

const int maxn = 10;
struct Node{
    int r, c, dir;
    Node(int r = 0, int c = 0, int dir = 0) : r(r), c(c), dir(dir) {}
};

int has_edge[maxn][maxn][4][3];
int d[maxn][maxn][4];
Node p[maxn][maxn][4];
int r0, c0, dir, r1, c1, r2, c2;

const char *dirs = "NESW";
const char *turns = "FLR";

int dir_id(char c)
{
    return strchr(dirs, c) - dirs;
}

int turn_id(char c)
{
    return strchr(turns, c) - turns;
}

bool check(int x, int y)
{
    if(x >= 1 && x <= 9 && y >= 1 && y <= 9) return true;
    else return false;
}

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};

Node walk(const Node &u, int turn){
    int dir = u.dir;
    if(turn == 1) dir = (dir + 3) % 4; //逆时针
    if(turn == 2) dir = (dir + 1) % 4; //顺时针
    return Node(u.r + dr[dir], u.c + dc[dir], dir);
}

void print_ans(Node u){
    vector <Node> nodes;
    for(;;){
        nodes.push_back(u);
        if(d[u.r][u.c][u.dir] == 0) break;
        u = p[u.r][u.c][u.dir];
    }
    nodes.push_back(Node(r0, c0, dir));
    int cnt = 0;
    for(int i = (int)nodes.size() - 1; i >= 0; i--){
        if(cnt % 10 == 0) printf(" ");
        printf(" (%d,%d)", nodes[i].r, nodes[i].c);
        if(++cnt % 10 == 0) printf("\n");
    }
    if(nodes.size() % 10 != 0) printf("\n");
}

void solve()
{
    queue <Node> q;
    memset(d, -1, sizeof(d));
    Node u(r1, c1, dir);
    d[r1][c1][dir] = 0;
    q.push(u);
    while(!q.empty())
    {
        Node u = q.front(); q.pop();
        if(u.r == r2 && u.c == c2){
            print_ans(u);
            return ;
        }
        for(int i = 0; i < 3; i++){
            Node v = walk(u, i);
            if(has_edge[u.r][u.c][u.dir][i] && check(v.r, v.c) && d[v.r][v.c][v.dir] < 0){
                d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1;
                p[v.r][v.c][v.dir] = u;
                q.push(v);
            }
        }
    }
    printf("  No Solution Possible\n");//注意前面有2个空格。。
}

//bool input()
//{
//    char s[99], s2[99];
//    if(scanf("%s%d%d%s%d%d", s, &r0, &c0, s2, &r2, &c2) != 6) return false;
//    printf("%s\n", s);
//    dir = dir_id(s2[0]);
//    r1 = r0 + dr[dir];
//    c1 = c0 + dc[dir];
//    memset(has_edge, 0, sizeof(has_edge));
//    for(;;){
//        int r, c;
//        scanf("%d", &r);
//        if(r == 0) break;
//        scanf("%d", &c);
//        while(scanf("%s", s) == 1 && s[0] != '*'){
//            for(int i = 1; i < (int)strlen(s); i++){
//                has_edge[r][c][dir_id(s[0])][turn_id(s[i])] = 1;
//            }
//        }
//    }
//    return true;
//}

bool read_case() {
  char s[99], s2[99];
  if(scanf("%s%d%d%s%d%d", s, &r0, &c0, s2, &r2, &c2) != 6) return false;
  printf("%s\n", s);
  dir = dir_id(s2[0]);
  r1 = r0 + dr[dir];
  c1 = c0 + dc[dir];

  memset(has_edge, 0, sizeof(has_edge));
  for(;;) {
    int r, c;
    scanf("%d", &r);
    if(r == 0) break;
    scanf("%d", &c);
    while(scanf("%s", s) == 1 && s[0] != '*') {
      for(int i = 1; i < strlen(s); i++)
        has_edge[r][c][dir_id(s[0])][turn_id(s[i])] = 1;
    }
  }
  return true;
}

int main()
{
    while(read_case())
    {
        solve();
    }
    return 0;
}

int n, m;
int maze[200][200], in[200], ans[200];

int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        if(n == 0 && m == 0) break;
        memset(maze, 0, sizeof(maze));
        memset(in, 0, sizeof(in));
        memset(ans, 0, sizeof(ans));
        int x, y;
        for(int i = 1; i <= m; i++){
            scanf("%d%d", &x, &y);
            maze[x][y] = 1;
            in[y]++;
        }
        int k = 0;
        queue <int> que;
        for(int i = 1; i <= n; i++){
            if(!in[i]) que.push(i);
        }
        while(que.size())
        {
            int u = que.front();
            que.pop();
            ans[++k] = u;
            for(int i = 1; i <= n; i++){
                if(maze[u][i]){
                    if(--in[i] == 0){
                        que.push(i);
                    }
                }
            }
        }
        for(int i = 1; i <= k; i++){
            printf("%d%c", ans[i], i == k ? '\n' : ' ');
        }
    }
    return 0;
}

const int maxn = 100;
int G[100][100], in[100], out[100], vis[100];
int idx(char x){
    return x - 'a';
}
void dfs(int u){
    vis[u] = 1;
    for(int i = 0; i < maxn; i++){
        if(G[u][i] && !vis[i]){
            dfs(i);
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        memset(G, 0, sizeof(G));
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        memset(vis, 0, sizeof(vis));
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            string line;
            cin>>line;
            int sz = line.size();
            int x = idx(line[0]), y = idx(line[sz - 1]);
            ++out[x];
            ++in[y];
            ++G[x][y];
        }
        bool flag = 1;
        int num1 = 0, num2 = 0;
        for(int i  = 0; i < maxn; i++) {
            if(!flag) break;
            if(in[i] != out[i]){
                if(in[i] == out[i] + 1) num1++;
                else if(in[i] + 1 == out[i]) num2++;
                else{
                    flag = false;
                    break;
                }
            }
        }
        if(num1 && num2 && num1 + num2 > 2) flag = false;
        if(flag)
        {
            for(int i = 0; i < maxn; i++){
                if(out[i]){
                    dfs(i);
                    break;
                }
            }
            bool ok = 1;
            for(int i = 0; i < maxn; i++){
                if(in[i] && !vis[i]){
                    ok = 0;
                    break;
                }
                if(out[i] && !vis[i]){
                    ok = 0;
                    break;
                }
            }
            if(ok){
                printf("Ordering is possible.\n");
            }
            else{
                printf("The door cannot be opened.\n");
            }
        }
        else{
            printf("The door cannot be opened.\n");
        }
    }
    return 0;
}

【6-18】 贴一个别人的解题链接吧。点击打开链接 看了很久才明白这种方法。

int g[maxn][maxn][maxn];
int x[maxn], y[maxn], z[maxn];
const int dx[] = {1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 1, -1, 0, 0};
const int dz[] = {0, 0, 0, 0, 1, -1};
map <int, int> X, Y, Z;
int n;
LL space, vol;
int xnum, ynum, znum, mx, my, mz;
struct node{
    int id;
    int x0, y0, z0, x, y, z;
    node(){}
    node(int id, int x0, int y0, int z0, int x, int y, int z):id(id), x0(x0), y0(y0), z0(z0), x(x), y(y), z(z){}
    bool operator<(const node &rhs) const{
        return x0 < rhs.x0 || (x0 == rhs.x0 && y0 < rhs.y0) || (x0 == rhs.x0 && y0 == rhs.y0 && z0 < rhs.z0);
    }
}r[maxn];
struct coord{
    int x, y, z;
    coord(){}
    coord(int x, int y, int z) : x(x), y(y), z(z) {}
};
void draw(int pos, int id){
    int x1 = X[r[pos].x0], x2 = X[r[pos].x0 + r[pos].x];
    int y1 = Y[r[pos].y0], y2 = Y[r[pos].y0 + r[pos].y];
    int z1 = Z[r[pos].z0], z2 = Z[r[pos].z0 + r[pos].z];
    for(int i = x1; i < x2; i++){
        for(int j = y1; j < y2; j++){
            for(int k = z1; k < z2; k++){
                g[i][j][k] = id;
            }
        }
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        memset(g, 0, sizeof(g));
        memset(x, 0, sizeof(x));
        memset(y, 0, sizeof(y));
        memset(z, 0, sizeof(z));
        X.clear();
        Y.clear();
        Z.clear();
        for(int i = 0; i < n; i++){
            scanf("%d%d%d%d%d%d", &r[i].x0, &r[i].y0, &r[i].z0, &r[i].x, &r[i].y ,&r[i].z);
            r[i].id = i + 1;
            x[i*2+1] = r[i].x0, x[i*2+2] = r[i].x0 + r[i].x;
            y[i*2+1] = r[i].y0, y[i*2+2] = r[i].y0 + r[i].y;
            z[i*2+1] = r[i].z0, z[i*2+2] = r[i].z0 + r[i].z;
        }
        sort(r, r + n);
        sort(x + 1, x + 2 * n + 1);
        sort(y + 1, y + 2*n + 1);
        sort(z + 1, z + 2*n + 1);
        xnum = unique(x + 1, x + 2 * n + 1) - (x + 1);
        ynum = unique(y + 1, y + 2 * n + 1) - (y + 1);
        znum = unique(z + 1, z + 2 * n + 1) - (z + 1);
        x[0] = y[0] = z[0] = -1;
        vol = space = 0;
        for(int i = 1; i <= xnum; i++) X[x[i]] = i;
        for(int i = 1; i <= ynum; i++) Y[y[i]] = i;
        for(int i = 1; i <= znum; i++) Z[z[i]] = i;
        for(int i = 0; i < n; i++){
            draw(i,  r[i].id);
        }
        vector <coord> v;
        v.push_back(coord(0, 0, 0));
        while(!v.empty())
        {
            coord cd = v.back(); v.pop_back();
            int x = cd.x, y = cd.y, z = cd.z;
            for(int i = 0; i < 6; i++){
                int tx = x + dx[i];
                int ty = y + dy[i];
                int tz = z + dz[i];
                if(tx >= 0 && tx <= xnum && ty >= 0 && ty <= ynum && tz >= 0 && tz <= znum && !g[tx][ty][tz]){
                    g[tx][ty][tz] = -1;
                    v.push_back(coord(tx, ty, tz));
                }
            }
        }
        for(int i = 1; i < xnum; i++){
            for(int j = 1; j < ynum; j++){
                for(int k = 1; k < znum; k++){
                    int l1 = x[i + 1] - x[i], l2 = y[j + 1] - y[j], l3 = z[k + 1] - z[k];
                    if(g[i][j][k] != -1) vol += l1*l2*l3;
                    for(int d = 0; d < 6; d++){
                        if(g[i][j][k] != -1 && g[i+dx[d]][j+dy[d]][k+dz[d]] == -1){
                            space += dx[d] ? l2 * l3 : dy[d] ? l1 * l3 : l1 * l2;
                        }
                    }
                }
            }
        }
        printf("%lld %lld\n", space, vol);
    }
    return 0;
}

那么如何判断正方形能否拼成一个无限大的结构呢？通过观察可以发现，如果可以的话，那么这个结构中的一些正方形一定会重复出现，即他们之间的拼接点会重复出现！在有向图中即存在有向环！因此，只需要判断最终形成的有向图中是否含有有向环即可，利用拓扑排序即可完成判断。

int G[maxn][maxn];
int idx(char a1, char a2)
{
    return (a1 - 'A') * 2 + (a2 == '+' ? 0 : 1);
}
void addedge(char a1, char a2, char b1, char b2)
{
    if(a1 == '0' || b1 == '0') return;
    int u = idx(a1, a2) ^ 1, v = idx(b1, b2);
    G[u][v] = 1;
}
int c[maxn];
bool dfs(int u){
    c[u] = -1;
    for(int v = 0;  v < maxn; v++){
        if(G[u][v]){
            if(c[v] < 0) return true;
            else if(!c[v] && dfs(v)) return true;
        }
    }
    c[u] = 1;
    return false;
}
bool topsort(){
    memset(c, 0, sizeof(c));
    for(int u = 0; u < maxn; u++){
        if(!c[u]){
            if(dfs(u)){
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int n;
    while(scanf("%d", &n) != EOF && n)
    {
        memset(G, 0, sizeof(G));
        while(n--){
            char s[10];
            scanf("%s", s);
            for(int i = 0; i < 4; i++){
                for(int j = 0; j < 4; j++){
                    if(i != j){
                        addedge(s[i*2], s[i*2+1], s[j*2], s[j*2+1]);
                    }
                }
            }
        }
        if(topsort())
        {
            printf("unbounded\n");
        }
        else{
            printf("bounded\n");
        }
    }
    return 0;
}

struct edge{
    int u, v, w;
    edge(){}
    edge(int u, int v, int w) : u(u), v(v), w(w){}
};

vector <edge> edges;
vector <int> G[maxn];
vector <int> ans;
int n, d[maxn], vis[maxn];

void addedge(int u, int v, int c){
    edges.push_back(edge(u, v, c));
    int sz = (int)edges.size() - 1;
    G[u].push_back(sz);
}

void dfs2()
{
    memset(vis, 0, sizeof(vis));
    d[n - 1] = 0;
    vis[n - 1] = 1;
    queue <int> que;
    que.push(n - 1);
    while(!que.empty())
    {
        int v = que.front();
        que.pop();

        for(int i = 0; i < G[v].size(); i++){
            int e = G[v][i];
            int u = edges[e].v;
            if(!vis[u]){
                vis[u] = 1;
                d[u] = d[v] + 1;
                que.push(u);
            }
        }
    }
}

void dfs1()
{
    memset(vis, 0, sizeof(vis));
    vis[0] = true;
    ans.clear();
    vector <int> nxt;
    nxt.push_back(0);
    for(int i = 0; i < d[0]; i++){
        int mincol = INF;
        for(int j = 0; j < nxt.size(); j++){
            int u = nxt[j];
            for(int k = 0; k < G[u].size(); k++){
                int e = G[u][k];
                int v = edges[e].v;
                if(d[u] == d[v] + 1){
                    mincol = min(mincol, edges[e].w);
                }
            }
        }
        ans.push_back(mincol);
        vector <int> nxt2;
        for(int j = 0; j < nxt.size(); j++){
            int u = nxt[j];
            for(int k = 0; k < G[u].size(); k++){
                int e = G[u][k];
                int v = edges[e].v;
                if(d[u] == d[v] + 1 && !vis[v] && edges[e].w == mincol){
                    nxt2.push_back(v);
                    vis[v] = 1;
                }
            }
        }
        nxt = nxt2;
    }
}

void print_ans()
{
    printf("%d\n", ans.size());
    printf("%d", ans[0]);
    for(int i = 1; i < ans.size(); i++){
        printf(" %d", ans[i]);
    }
    printf("\n");
}

int main()
{
    int m, x, y, z;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        edges.clear();
        for(int i = 0; i < n; i++) G[i].clear();
        while(m--)
        {
            scanf("%d%d%d", &x, &y, &z);
            addedge(x - 1, y - 1, z);
            addedge(y - 1, x - 1, z);
        }
        dfs2();
        dfs1();
        print_ans();
    }
    return 0;
}

【6-22】脑洞题，非常有趣。这个在分类里面叫对偶图。本题初看起来比较麻烦，不妨简化一下：先判断是否有解，再考虑如何求出解。根据题意描述，相当于在一个正方形中有若干个圆形障碍物，问是否能从左边界走到右边界。判断是否有解需要一点创造性的思维：不妨把正方形当做一个湖，所有的圆形都是垫脚石，假设我们可以从上边界“踩着”垫脚石成功走到下边界，说明左右边界是不连通的；否则就是连通的。想到了这里，便不难用dfs或bfs来判断是否有解了：每次都从和上边界相交的圆开始进行dfs，如果遇到某个圆和下边界也相交，那么无解。那么如何寻找解呢，根据题意需要找到最靠近北边的。这样的话，只需要找到所有与左边界相交的圆中最靠南边的交点即可，同理可以找到右边界的解。本题在数据处理上有一个小技巧：把圆形设计成一个结构体，维护圆心坐标和半径，同时用read成员函数读入数据，比用scanf函数方便了很多。

struct Circle{
    int x, y, r;
    void read(){
        scanf("%d%d%d", &x, &y, &r);
    }
}c[maxn];
double ans1, ans2;
int n, vis[maxn];
bool jiao(Circle a, Circle b){
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return dx * dx + dy * dy - (a.r + b.r) * (a.r + b.r) <= 0;
}
bool dfs(int u){
    vis[u] = 1;
    if(c[u].y - c[u].r <= 0) return false;
    //和左边界有交点
    if(c[u].x - c[u].r <= 0) ans1 = min(ans1, c[u].y - sqrt(c[u].r * c[u].r - c[u].x * c[u].x));
    //和右边界有交点
    if(c[u].x + c[u].r >= 1000) ans2 = min(ans2, c[u].y - sqrt(c[u].r * c[u].r - (1000 - c[u].x) * (1000 - c[u].x)));
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            if(jiao(c[u], c[i])){
                if(!dfs(i)){
                    return false;
                }
            }
        }
    }
    return true;
}

void work(){
    ans1 = ans2 = 1000.00;
    for(int i = 0; i < n; i++){
        if(!vis[i] && c[i].y + c[i].r >= 1000){
            if(!dfs(i)){
                printf("IMPOSSIBLE\n");
                return ;
            }
        }
    }
    printf("0.00 %.2f 1000.00 %.2f\n", ans1, ans2);
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; i++){
            c[i].read();
        }
        work();
    }
    return 0;
}