Frame Stacking POJ - 1128

原题链接

考察:拓扑排序 dfs

我觉得这道题最难的是理解题目...

这道题的字母是随机使用,不一定按顺序

思路:

我们先要在相片中找到各字母的边框.这里只能暴力查找.找到后遍历边框如果边框不是该字母,说明此字母是下面的边框.利用拓扑排序加边即可.

比较难的点是dfs遍历拓扑排序.本蒟蒻是看了别人的dfs才写出来.总之也和bfs差不多.我们必须先找到无根节点的结点.然后删去与它有关的边.再dfs寻找下一个无根的结点

1 #include <iostream> 2 using namespace std; 3 const int N = 910; 4 int hx,w; 5 bool vis[28]; 6 char mp[35][35]; 7 int h[N],e[N],ne[N],d[N],idx,n,m,xmp[35][35],cnt,path[28]; 8 struct alp{ 9     int x1,y1,x2,y2;10     bool use;11 }alpha[30];12 void inits()13 {14     fill(d,d N,0); fill(h,h N,-1);15     idx = 0; cnt = 0;16     fill(vis,vis 28,0);17     for(int i=1;i<=26;i  ) alpha[i].use=0,alpha[i].x1=N,alpha[i].y1=N,alpha[i].y2=0,alpha[i].x2=0;18 }19 void add(int a,int b)20 {21     e[idx]=b,ne[idx]=h[a],h[a]=idx  ; d[b]  ;22 }23 void dfs(int k)24 {25     if(k==cnt){26         for(int i=0;i<k;i  ) printf("%c",path[i] 'A'-1);27         printf("\n");28     }else{29         for(int i=1;i<=26;i  ){30             if(!d[i]&&!vis[i]&&alpha[i].use)31             {32                 path[k]=i;33                 for(int j=h[i];j!=-1;j=ne[j]) d[e[j]]--;34                 vis[i]=1;35                 dfs(k 1);36                 vis[i]=0;37                 for(int j=h[i];j!=-1;j=ne[j]) d[e[j]]  ;38             }39         }40     }41 }42 int main()43 {44     while(scanf("%d%d",&hx,&w)!=EOF)45     {46         inits();47         for(int i=1;i<=hx;i  ){48             for(int j=1;j<=w;j  ){49                 cin>>mp[i][j];50                 if(mp[i][j]!='.') {51                     xmp[i][j]=mp[i][j]-'A' 1;52                     alpha[xmp[i][j]].x1 = min(alpha[xmp[i][j]].x1,i);53                     alpha[xmp[i][j]].y1 = min(alpha[xmp[i][j]].y1,j);54                     alpha[xmp[i][j]].x2 = max(alpha[xmp[i][j]].x2,i);55                     alpha[xmp[i][j]].y2 = max(alpha[xmp[i][j]].y2,j);56                     alpha[xmp[i][j]].use = true;57                 }58             }59         }//题目中每个字母都有可能出现,但不是按顺序的 60         for(int i=1;i<=26;i  ){61             if(alpha[i].use){62                 cnt  ;63                 for(int j=alpha[i].y1;j<=alpha[i].y2;j  )64                     if(xmp[alpha[i].x1][j]!=i) add(i,xmp[alpha[i].x1][j]);65                 for(int j=alpha[i].y1;j<=alpha[i].y2;j  )66                     if(xmp[alpha[i].x2][j]!=i) add(i,xmp[alpha[i].x2][j]);67                 for(int j=alpha[i].x1;j<=alpha[i].x2;j  )68                     if(xmp[j][alpha[i].y1]!=i) add(i,xmp[j][alpha[i].y1]);69                 for(int j=alpha[i].x1;j<=alpha[i].x2;j  )70                     if(xmp[j][alpha[i].y2]!=i) add(i,xmp[j][alpha[i].y2]);71             }72         }73         dfs(0);74     } 75     return 0;76 }

来源:https://www.icode9.com/content-4-818101.html

(0)

相关推荐

  • SPFA学习

    作者:胡东麒 ID:国服墨子 学校:长沙市砂子塘小学 六年级 博客地址:https://www.luogu.com.cn/blog/359614/ Step 1:基本的SPFA最短路 Step 1 - ...

  • 算法创作|蓝桥杯——排列序数问题解决方法

    问题描述示例:如果用a b c d这4个字母组成一个串,有4!=24种,如果把它们排个序,每个串都对应一个序号:abcd  0abdc  1acbd  2acdb  3adbc  4adcb  5ba ...

  • 经方临床医案练习【第1128期】

    伤寒论经方学堂 1周前 今日练习 张某某,女,58岁. 患者四年来夜不能寐,每晚靠服安定片或水合氯醛等西药维持,才能入睡2-3h,但稍闻声响,便醒而不寐,屡治鲜效. 近20天来彻夜不寐,虽加倍服用安定 ...

  • 东风动百物,草木尽欲言 | 本草江湖第1128期

    泽漆 01 2 芫花 大戟 03 4 番木瓜 腹水草 05 6 断肠草开花了 猫须草 07 8 猕猴桃根 何首乌 09 10 荆芥苗 铁扁担 11 12铁苋菜 白鹤灵芝 13 14 地稔 丰花草 15 ...

  • 困境破局:银发经济浪潮下,1128家传统老字号品牌迎来新机会

    银发经济下,老字号品牌迎来"新商机". 中华老字号数量已从新中国成立初期的10000多家,减少至目前的1128家,这其中,只有10%能盈利,90%面临着不同程度的经营困境. 而加速 ...

  • 《梁健续集》第1-128章

    <梁健续集:再启征程>是<权路迷局>续集,与前部无缝衔接. 点击下方<蓝色目录>即可点开文章 <梁健续集>第001章 解开谜底 <梁健续集> ...

  • 一、问候亲友三月初十早上好!(大狮代办1128)

    作者:护虎哥 一.说说小时候的歌(大狮代办1128) 月亮在白莲花般的云朵里穿行,晚风吹来一阵阵快乐的歌声,我们坐在高高的谷堆旁边,听妈妈讲那过去的事情-- 小时候,我们喜欢唱这首歌,唱着唱着,自己成 ...

  • [html] 第117天 frame和iframe有什么区别?

    今日试题: frame和iframe有什么区别? 此开源项目四大宗旨:勤思考,多动手,善总结,能坚持 <论语>,曾子曰:"吾日三省吾身"(我每天多次反省自己). 前端面 ...

  • 周期下降到2板,耐心等待龙头出现(1128)

    做股票如同上学,小学要学K线.均线,初中要学基本面分析.各种技术指标,高中要学各种形态模式,大学则要学情绪周期.学逻辑思维... 当然有些人把K线学好了,也能赚到钱,把形态学好了,也能赚到钱... 而 ...

  • 11-28郭哥晚评:行情曙光初现,股市遍地黄金!

    粉丝福利 大盘思路 行情解析: 今天上证指数早盘上攻未果,跳水下杀.前期强势股回调明显.但是在10点整数关口时由券商板块拉升护盘,而创业板以宁德时代,迈瑞医疗,东方财富的权重与创业板50成分拉升.量能 ...

  • 11-28收评:深港通开通在即,冲击终点的最后一蹲!

    盘面小结 万众瞩目的深港通千呼万唤始出来,但是今天市场走势相对比较平静,没有高开高走的大阳线,依然是分化严重的二八行情.中字头个股表现抢眼,安邦举牌的中国建筑强势涨停,权重股有效的拉动了指数上行,但是 ...