USACO 4.4 Frame Up

The problem description mentions:

• It is possible to see at least one part of each of the four sides of a frame.

With the information of the position of each side, we can calculate the position of each frame, as each frame can be determined by its left/down and right/up (or left/up right/down) corner. The relationship of frame B stacks on top of frame A can be modeled as a directed graph where A and B are vertices and there is an edge from A to B. Then do a topological sort pass to generate the result. Note it requires all possible results of topological sort, which requires back tracking with DFS. A good reference implementation of such algorithm can be found here.

#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>

using namespace std;

int H, W;
vector<int> min_x(30, -1);
vector<int> min_y(30, -1);
vector<int> max_x(30, -1);
vector<int> max_y(30, -1);
vector<bool> exist(30, false);
char grid[33][33]; // processed input.
int g[30][30]; // matrix representation of graph.
vector<int> in_degree(30, 0);
ifstream fin("frameup.in");
ofstream fout("frameup.out");

int ans[30], nans = 0;

void buildGraph() {
    fin >> H >> W;
    for(int i = 0; i < H; ++i) {
        fin >> grid[i];
        for(int j = 0; j < W; ++j) {
            cout << grid[i][j];
            if(grid[i][j] == '.') continue;
            int v = grid[i][j] - 'A';
            if(min_x[v] == -1 || min_x[v]>i) min_x[v] = i;
            if(min_y[v] == -1 || min_y[v]>j) min_y[v] = j;
            if(max_x[v] == -1 || max_x[v]<i) max_x[v] = i;
            if(max_y[v] == -1 || max_y[v]<j) max_y[v] = j;
            exist[v] = true;
        }
        cout << endl;
    }
    
    for(int u = 0; u < 26; ++u) {
        if (!exist[u]) continue;
        for(int y = min_y[u]; y <= max_y[u]; ++y) {
            int v = grid[min_x[u]][y] - 'A';
            if(v != u && !g[u][v]) {
                g[u][v] = 1; ++in_degree[v];
            }
            
            v = grid[max_x[u]][y] - 'A';
            if(v != u && !g[u][v]) {
                g[u][v] = 1; ++in_degree[v];
            }
        }
        
        for(int x = min_x[u]; x <= max_x[u]; ++x) {
            int v = grid[x][min_y[u]] - 'A';
            if(v != u && !g[u][v]) {
                g[u][v] = 1; ++in_degree[v];
            }
            v = grid[x][max_y[u]] - 'A';
            if(v != u && !g[u][v]) {
                g[u][v] = 1; ++in_degree[v];
            }
        }
    }
}

// DFS that generates all topological sorts in alphabetic order.
void dfs() {
    bool all_used = true;
    for(int i = 0; i < 26; ++i) {
        if(exist[i]) {
            all_used = false;
            break;
        }
    }
    
    if(all_used) {
        for(int i = 0; i < nans; ++i) {
            fout << (char)(ans[i] + 'A');
            cout << (char)(ans[i] + 'A');
        }
        fout << endl; cout << endl;
        return;
    }
    
    for(int u = 0; u < 26; ++u) {
        if (!exist[u]) continue;
        if (in_degree[u]) continue;
        exist[u] = false;
        ans[nans++] = u;
        for(int v = 0; v < 26; ++v) {
            if(g[u][v]) --in_degree[v];
        }
        dfs();
        exist[u] = true;
        nans--;
        for(int v = 0; v < 26; ++v) {
            if(g[u][v]) in_degree[v]++;
        }
    }
}

int main() {
    buildGraph();
    dfs();
    return 0;
}