Frame Stacking
2024-08-26 12:29:12
poj1128:http://poj.org/problem?id=1128
题意:一个二维图里面有几个相框(四条边的空心矩形框)。有重叠,求重叠顺序。还有题目保证至少存在一种符合要求的序列,当有多种情况时按字典序由小到大输出所有的情况。
题解:建图然后+topsort+dfs ,建图很麻烦的,要细心处理。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include <iterator>//stl迭代器
using namespace std;
char map[][];//记录原图
int g[][];//topsort的图
int counts[];//记录入度
int n,m,num;// 行和列 以及出现过的字母的个数
bool visit[];//记录出现过的字母
vector<char> ans;//记录结果
struct Node{
int x1,y1;
int x2,y2;
}edge[];//储存每个节点出现的最左,最右,最上,最下的坐标。
void init(){
num=;//初始化
memset(g,,sizeof(g));
memset(map,,sizeof(map));
for(int i=;i<=;i++){
counts[i]=;
visit[i]=false;
edge[i].x1=edge[i].y1=;
edge[i].x2=edge[i].y2=-;
}
}
void build1(){//建图
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
cin>>map[i][j];
if(map[i][j]!='.'){
if(!visit[map[i][j]-'A'+]){
num++;
visit[map[i][j]-'A'+]=true;
}//统计出现过的字母
if(edge[map[i][j]-'A'+].x1>i){
edge[map[i][j]-'A'+].x1=i;
}
if(edge[map[i][j]-'A'+].y1>j){
edge[map[i][j]-'A'+].y1=j;
}
if(edge[map[i][j]-'A'+].x2<i){
edge[map[i][j]-'A'+].x2=i;
}
if(edge[map[i][j]-'A'+].y2<j){
edge[map[i][j]-'A'+].y2=j;
}//不断更新各个图片的上下左右的值 }
}
}
void build2(){//开始建topsort的图g
for(int i=;i<=;i++){
if(visit[i]){//如果出现过
for(int j=edge[i].y1;j<=edge[i].y2;j++){//遍历第一行(最上面的一行)找出与该图不同的图,如果不同
if(map[edge[i].x1][j]!=i+'A'-&&!g[i][map[edge[i].x1][j]-'A'+]){
g[i][map[edge[i].x1][j]-'A'+]=;//如果没有建边,而且满足覆盖关系
counts[map[edge[i].x1][j]-'A'+]++;
}
}
for(int j=edge[i].y1;j<=edge[i].y2;j++){//最下面的一行
if(map[edge[i].x2][j]!=i+'A'-&&!g[i][map[edge[i].x2][j]-'A'+]){
g[i][map[edge[i].x2][j]-'A'+]=;
counts[map[edge[i].x2][j]-'A'+]++;
}
}
for(int j=edge[i].x1;j<=edge[i].x2;j++){//最左边的一列
if(map[j][edge[i].y1]!=i+'A'-&&!g[i][map[j][edge[i].y1 ]-'A'+]){
g[i][map[j][edge[i].y1]-'A'+]=;
counts[map[j][edge[i].y1]-'A'+]++;
}
}
for(int j=edge[i].x1;j<=edge[i].x2;j++){//最右边的一列
if(map[j][edge[i].y2]!=i+'A'-&&!g[i][map[j][edge[i].y2]-'A'+]){
g[i][map[j][edge[i].y2]-'A'+]=;
counts[map[j][edge[i].y2]-'A'+]++;
}
}
}
}
}
void topo(int depth, int count){//排序,depth记录已经处理的字符的个数,count为总的字符个数 if (depth >= count){//达到开始值就开始输出
copy(ans.begin(), ans.end(), ostream_iterator<char>(cout));
cout << endl;
return;
}//
for (int i = ; i <=; ++i){
if(visit[i]){
if (counts[i] == ){
ans.push_back(i+'A'-);
counts[i] = -;
for (int k = ; k <=; ++k){
if (g[i][k] == ){
counts[k]--;
}
}
//递归向下
topo(depth+, count);
ans.pop_back();//恢复现场1是ans里面的值要删除,2是各个点的入度要恢复+1;
counts[i] = ;
for (int k = ; k <=; ++k){
if (g[i][k] == ){
counts[k]++;
}
}
}
}
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
ans.clear();//清除
build1();
build2();
topo(,num);//从0开始
}
}
最新文章
- SVN源代码的版本控制系统使用简介
- mysql:添加索引
- 3分钟,9个Q&;A让你快速知道Docker到底是什么
- Android shell命令查询ip,网关,DNS
- Unity键值(KeyCode)
- CSS 动画之十-图片+图片信息展示
- Ogre初入手:最简单的ogre程序骨架
- http://blog.csdn.net/yaerfeng/article/details/27683813
- Flume-ng+Kafka+storm的学习笔记
- 关于Oracle过程,函数的经典例子及解析
- [CF 474E] Pillars (线段树+dp)
- Performance testing of web application
- 开发自己PHP MVC框架(一)
- 一步一步学EF系列1【Fluent API的方式来处理实体与数据表之间的映射关系】
- 微信小程序PHP 微信支付接口调用
- 1: java开发_";";和null的区别
- 【docker】将容器中数据拷贝到主机
- 利用 Azure Devops 创建和发布 Nuget 包
- Design and Implementation of a Routing Control Platform阅读笔记
- 初识:JMX