Window Pains(poj 2585)
2024-08-26 02:00:21
题意:
一个屏幕要同时打开9个窗口,每个窗口是2*2的矩阵,整个屏幕大小是9*9,每个窗口位置固定。
但是是否被激活(即完整显示出来)不确定。
给定屏幕状态,问是否可以实现显示。
分析:拓扑排序,把完全出现的数字拿出来,位置置空,然后再找下一个完全出现的数,直到找完为止,若中途找不到,则不合法。
代码:
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int map[],pos[][],vis[];
void init()
{
int i=,j=;
while(i<=)
{
pos[i][]=j;pos[i][]=j+;pos[i][]=j+;pos[i][]=j+;
if(i%==)j+=;
else j+=;
i++;
}
}
bool ok(int x)
{
for(int i=;i<=;i++)
if(map[pos[x][i]]!=x&&map[pos[x][i]]!=)
return false;
return true;
}
void work()
{
int tot=;
while()
{
int k=;
for(int i=;i<=;i++)
if(!vis[i]&&ok(i))
{
tot++;
vis[i]=;
k=i;
break;
}
if(!k)break;
for(int i=;i<=;i++)
map[pos[k][i]]=;
}
if(tot<)printf("THESE WINDOWS ARE BROKEN\n");
else printf("THESE WINDOWS ARE CLEAN\n");}int main(){
init();
while()
{
memset(vis,,sizeof(vis));
string s;cin>>s;
if(s[]=='O')break;
for(int i=;i<=;i++)
scanf("%d",&map[i]);
work();
cin>>s;
}
return ;
}
最新文章
- C语言的概述--学习c的第二天
- Maven-在eclipse中安装Maven插件
- docker-compose常用命令
- Docker Machine
- js高级教程第3版笔记(我的理解)陆续更新中
- JS原型的剖析与理解
- C#串口扫描
- 一步一步学android之控件篇——ScrollView
- hdu_5085_Counting problem(莫队分块思想)
- js删除最后一个字符串方法
- (一)Redis在windows下的安装和使用
- HNOI2015 Day 1
- ajax全局事件
- 轻松3步设置sublime text2/sublime text3的预览浏览器
- Vue和React的对比
- 基于mindwave脑电波进行疲劳检测算法的设计(1)
- java System.arraycopy()
- 超感猎杀/超感八人组第一季至二季/全集Sense8迅雷下载
- myeclipse安装jad反编译插件
- Django之Models的class Meta