[P2741][USACO4.4]重叠的图像Frame Up

· · 题解

题目

        点这里看题目。

分析

        很容易看出来，这道题是拓扑排序的题。
        我们扫描一个矩形a的边，如果发现上面有矩形b的代表字母，我们就可以确定b的顺序在a之后，从b向a连一条边。这样就可以构造出一个DAG。
        不过，由于题目要求输出所有的顺序，所以我们跑拓扑序的时候得用DFS，每次从整个图中选择一个入度为0的点进行下一次搜索，而不是用队列头的点。
        另外，按照上述方法连边，得到的顺序是反序，总之得在排序之前把顺序调整正确。
        其他的看代码。

代码

#include <queue>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXH = 305, MAXW = 35, MAXSIZ = 30;

template<typename _T>
void read( _T &x )
{
    x = 0;char s = getchar();int f = 1;
    while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
    while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
    x *= f;
}

template<typename _T>
void write( _T x )
{
    if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
    if( 9 < x ){ write( x / 10 ); }
    putchar( x % 10 + '0' );
}

template<typename _T>
_T MIN( const _T a, const _T b )
{
    return a < b ? a : b;
}

template<typename _T>
_T MAX( const _T a, const _T b )
{
    return a > b ? a : b;
}

struct edge
{
    int to, nxt;
}Graph[MAXSIZ * MAXSIZ / 2];

struct circle
{
    int lx, ly, rx, ry;
    circle()
    {
        lx = ly = 10005;
        rx = ry = -1;
    }
}a[MAXSIZ];

vector<string> res;

int dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
int head[MAXSIZ], into[MAXSIZ];
int mp[135];
char remp[MAXSIZ], tmp[MAXSIZ];
char board[MAXH][MAXW];
int H, W, cnt, tot;
bool used[MAXSIZ] = {};

void addEdge( const int from, const int to )
{
    cnt ++;
    Graph[cnt].to = to;
    Graph[cnt].nxt = head[from];
    into[to] ++;
    head[from] = cnt;
}

string trans( const char* str )
{
    string ans = "";
    for( int i = tot ; i >= 1 ; i -- )
    {
        ans.push_back( str[i] );
    }
    return ans;
}

void DFS( const int dep )
{
    if( dep > tot )
    {
        res.push_back( trans( tmp ) );
        return;
    }
    for( int i = 1 ; i <= tot ; i ++ )
    {
        if( ! used[i] && ! into[i] )
        {
            used[i] = true;
            for( int j = head[i] ; j ; j = Graph[j].nxt )
            {
                into[Graph[j].to] --;
            }
            tmp[dep] = remp[i];
            DFS( dep + 1 );
            used[i] = false;
            for( int j = head[i] ; j ; j = Graph[j].nxt )
            {
                into[Graph[j].to] ++;
            }
        }
    }
}

int main()
{
    int indx;
    read( H ), read( W );
    for( int i = 1 ; i <= H ; i ++ )
    {
        scanf( "%s", board[i] + 1 );
        for( int j = 1 ; j <= W ; j ++ )
        {
            if( 'A' <= board[i][j] && board[i][j] <= 'Z' && ! mp[board[i][j]] )
            {
                mp[board[i][j]] = ++tot;
                remp[tot] = board[i][j];
            }
            indx = mp[board[i][j]];
            a[indx].lx = MIN( a[indx].lx, i );
            a[indx].ly = MIN( a[indx].ly, j );
            a[indx].rx = MAX( a[indx].rx, i );
            a[indx].ry = MAX( a[indx].ry, j );
        }
    }
    for( int i = 1 ; i <= tot ; i ++ )
    {
        for( int j = a[i].lx ; j <= a[i].rx ; j ++ )
        {
            indx = mp[board[j][a[i].ly]];
            if( indx ^ i ) addEdge( indx, i );
            indx = mp[board[j][a[i].ry]];
            if( indx ^ i ) addEdge( indx, i );
        }
        for( int j = a[i].ly ; j <= a[i].ry ; j ++ )
        {
            indx = mp[board[a[i].lx][j]];
            if( indx ^ i ) addEdge( indx, i );
            indx = mp[board[a[i].rx][j]];
            if( indx ^ i ) addEdge( indx, i );
        }
    }
    DFS( 1 );
    ios :: sync_with_stdio( false );
    sort( res.begin(), res.end() );
    for( int i = 0 ; i < res.size() ; i ++ )
    {
        cout << res[i] << endl;
    }
    return 0;
}