zoj 1083 Frame Stacking

95 阅读 0 评论 63 点赞

我是靠谱客的博主朴实凉面，最近开发中收集的这篇文章主要介绍zoj 1083 Frame Stacking，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int SIZE=30,NUM=26;

struct square
{
	int up, right, down, left;
}alpha[NUM];

int N,M,cnt,id[NUM];//cnt 图的种类数目，id[i]表示顶点i的入度
bool cover[SIZE][SIZE][NUM],map[NUM][NUM],exist[NUM];//cover[i][j][k]表示(i, j)处可以是图片k,map[i][j]表示图片i在图片j的下方;exist[i]表示i是否存在于给定的图中
char pic[SIZE][SIZE+1],seq[NUM];//seq储存的是得到的拓扑序列

void read_map()
{
	cnt=0;
	memset(exist, 0, sizeof exist);
	memset(alpha, -1, sizeof alpha);

	for(int i=0;i<N;++i)
     {
		scanf("%s",pic[i]);
		for(int j=0;j<M;++j)
               if(pic[i][j]!='.')
               {
                    int tmp=pic[i][j]-'A';
                    if(!exist[tmp])
                    {
                         exist[tmp]=1;
                          ++cnt;
                    }
                    //记录某个图片的上下边界。
                    if(alpha[tmp].up == -1 || i < alpha[tmp].up)
                         alpha[tmp].up = i;
                    if(alpha[tmp].down == -1 || i > alpha[tmp].down)
                         alpha[tmp].down = i;
                    if(alpha[tmp].left == -1 || j < alpha[tmp].left)
                         alpha[tmp].left = j;
                    if(alpha[tmp].right == -1 || j > alpha[tmp].right)
                         alpha[tmp].right = j;
               }
	}
}

void inite()
{
     int i, j;
     for(i=0;i<NUM;++i)     //复原每一个图片
          if(exist[i])
          {//如果第i个图存在则把图i的边界都赋值为1（由于图是环形的特性）
               for(j = alpha[i].left; j <= alpha[i].right; ++j)//把两个上下边标记为1;
                    cover[ alpha[i].up ][j][i] = cover[ alpha[i].down ][j][i] = 1;
               for(j = alpha[i].up + 1; j < alpha[i].down; ++j)//把左右两个边标记为1;
                    cover[j][ alpha[i].left ][i] = cover[j][ alpha[i].right ][i] = 1;
          }
}
void build_map()
{
	int i,j,k;

	memset(cover,0,sizeof cover);
	memset(id,0,sizeof id);
	memset(map,0,sizeof map);

	inite();

     for(i=0; i<N; ++i)
     {
		for(j=0; j<M; ++j)
		{
		     if(pic[i][j] != '.')
               {
                    int tmp = pic[i][j]-'A';//第(i, j)位置，存放的类型

                    for(k = 0; k < NUM; ++k)//建立有向图
                         if(tmp != k && cover[i][j][k] && !map[k][tmp])
                         {
                              map[k][tmp] = 1;
                              ++id[tmp];
                         }
               }
		}
	}
}

void toposort(int cur)//cur表示在拓扑序列中存在的元素个数;利用了深搜的特性
{
	int i,j;
	if(cur == cnt)
     {
		for(i = 0; i<cur; ++i)
               putchar(seq[i]);
		puts("");
		return ;
	}

	for(i = 0; i < NUM; ++i)
          if(exist[i] && !id[i])//找入度为零的顶点，也即是在当前情况下，最底下的定点;
          {
               id[i] = -1;
               seq[cur] = i+'A';
               for(j = 0;j < NUM; ++j)
                    if(map[i][j])
                         --id[j];

               toposort(cur+1);

               id[i] = 0;
               for(j=0; j<NUM; ++j)
                    if(map[i][j])
                         ++id[j];
          }
}

int main()
{
	while(~scanf("%d %d",&N,&M))
     {
		read_map();
		build_map();
		toposort(0);
	}

	return 0;
}