POJ 2585 Window Pains(窗口的颜色显示问题,拓扑排序,经典题目)

本文主要是介绍POJ 2585 Window Pains(窗口的颜色显示问题,拓扑排序,经典题目),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Window Pains(点击>>原POJ)
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 1980 Accepted: 998

Description

Boudreaux likes to multitask, especially when it comes to using his computer. Never satisfied with just running one application at a time, he usually runs nine applications, each in its own window. Due to limited screen real estate, he overlaps these windows and brings whatever window he currently needs to work with to the foreground. If his screen were a 4 x 4 grid of squares, each of Boudreaux's windows would be represented by the following 2 x 2 windows: 
11..
11..
....
....
.22.
.22.
....
....
..33
..33
....
....
....
44..
44..
....
....
.55.
.55.
....
....
..66
..66
....
....
....
77..
77..
....
....
.88.
.88.
....
....
..99
..99
When Boudreaux brings a window to the foreground, all of its squares come to the top, overlapping any squares it shares with other windows. For example, if window  1 and then window  2 were brought to the foreground, the resulting representation would be:
122?
122?
????
????
If window 4 were then brought to the foreground:
122?
442?
44??
????
. . . and so on . . . 
Unfortunately, Boudreaux's computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly. And this is where you come in . . .

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets. 

A single data set has 3 components: 
  1. Start line - A single line: 
    START 

  2. Screen Shot - Four lines that represent the current graphical representation of the windows on Boudreaux's screen. Each position in this 4 x 4 matrix will represent the current piece of window showing in each square. To make input easier, the list of numbers on each line will be delimited by a single space. 
  3. End line - A single line: 
    END 

After the last data set, there will be a single line: 
ENDOFINPUT 

Note that each piece of visible window will appear only in screen areas where the window could appear when brought to the front. For instance, a 1 can only appear in the top left quadrant.

Output

For each data set, there will be exactly one line of output. If there exists a sequence of bringing windows to the foreground that would result in the graphical representation of the windows on Boudreaux's screen, the output will be a single line with the statement: 

THESE WINDOWS ARE CLEAN 

Otherwise, the output will be a single line with the statement: 
THESE WINDOWS ARE BROKEN 

Sample Input

START
1 2 3 3
4 5 6 6
7 8 9 9
7 8 9 9
END
START
1 1 3 3
4 1 3 3
7 7 9 9
7 7 9 9
END
ENDOFINPUT

Sample Output

THESE WINDOWS ARE CLEAN
THESE WINDOWS ARE BROKEN

Source

South Central USA 2003


i题意:

显示颜色的问题,一种颜色有一种显示的区域,大的可以覆盖小的。给定几个矩阵,问显示效果怎么样,好的话输出一句,否则输出另外一句。

具体参考书籍《图论》哈工大出版社。


i思路:

每个显色的数字位置如图:

这可是学姐在黑板上一点点画出来的图(这是我用EXCEL打的),讲题挺认真的,负责。



i参考代码:

实现方式:二维数组

#include<stdio.h>
#include<string.h>
const int MYDD=1103;int indegree[MYDD];
int map[113][113];
int dx[]= {0,1,0,1};
int dy[]= {0,0,1,1}; //移动的方向,注意不同于搜索
int local[10][2]= {-1,-1, 0,0, 0,1, 0,2, 1,0, 1,1, 1,2, 2,0, 2,1, 2,2};
//窗口的固定位置
bool TopoSort() {int now,flag;// now 当前选中的节点;flag 标记合法性for(int j=1; j<=9; j++) {flag=0;for(int i=1; i<=9; i++) {if(!indegree[i]) {flag=1;now=i;break;//入度为 0 即前驱}}if(!flag)   return false;indegree[now]=-1;//标记前驱数量为 -1for(int i=1; i<=9; i++)//当前节点的后继节点入度 -1if(map[now][i])     indegree[i]--;}return true;
}int main() {char C[32];while(1) {scanf("%s",C);if(!strcmp(C,"ENDOFINPUT"))	break;//结束测试数据memset(indegree,0,sizeof(indegree));//数组的初始化memset(map,0,sizeof(map));int screen[16][16];for(int j=0; j<4; j++)for(int k=0; k<4; k++)scanf("%d",&screen[j][k]);scanf("%s",C);for(int j=1; j<=9; j++) {for(int k=0; k<4; k++) {int gx=local[j][0]+dx[k];int gy=local[j][1]+dy[k];int now=screen[gx][gy];//当前屏幕显示的数字if(now!=j&&!map[j][now]) {map[j][now]=1;indegree[now]++;}}
//				printf("**********\n");}if(TopoSort())      puts("THESE WINDOWS ARE CLEAN");else                puts("THESE WINDOWS ARE BROKEN");}return 0;
}


这篇关于POJ 2585 Window Pains(窗口的颜色显示问题,拓扑排序,经典题目)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/489805

相关文章

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

PostgreSQL中rank()窗口函数实用指南与示例

《PostgreSQL中rank()窗口函数实用指南与示例》在数据分析和数据库管理中,经常需要对数据进行排名操作,PostgreSQL提供了强大的窗口函数rank(),可以方便地对结果集中的行进行排名... 目录一、rank()函数简介二、基础示例:部门内员工薪资排名示例数据排名查询三、高级应用示例1. 每

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.