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开始
}
}

最新文章

  1. SVN源代码的版本控制系统使用简介
  2. mysql:添加索引
  3. 3分钟,9个Q&amp;A让你快速知道Docker到底是什么
  4. Android shell命令查询ip,网关,DNS
  5. Unity键值(KeyCode)
  6. CSS 动画之十-图片+图片信息展示
  7. Ogre初入手:最简单的ogre程序骨架
  8. http://blog.csdn.net/yaerfeng/article/details/27683813
  9. Flume-ng+Kafka+storm的学习笔记
  10. 关于Oracle过程,函数的经典例子及解析
  11. [CF 474E] Pillars (线段树+dp)
  12. Performance testing of web application
  13. 开发自己PHP MVC框架(一)
  14. 一步一步学EF系列1【Fluent API的方式来处理实体与数据表之间的映射关系】
  15. 微信小程序PHP 微信支付接口调用
  16. 1: java开发_&quot;&quot;和null的区别
  17. 【docker】将容器中数据拷贝到主机
  18. 利用 Azure Devops 创建和发布 Nuget 包
  19. Design and Implementation of a Routing Control Platform阅读笔记
  20. 初识:JMX

热门文章

  1. DSPack各种使用方法
  2. Java基础知识强化之集合框架笔记14:List集合存储字符串并遍历
  3. label_设置行距、字距及计算含有行间距的label高度
  4. SQL Server 事务、异常
  5. opencar二次开发常用代码
  6. 在往oracle中插数据时,如何处理excel读取的时间空值
  7. OSX安装nginx和rtmp模块(rtmp直播服务器搭建)
  8. javascript社交平台分享-新浪微博、QQ微博、QQ好友、QQ空间、人人网
  9. winform(C#)拖拽实现获得文件路径
  10. What is SaaS?