Window Pains poj-2585

    题目大意:给出一个4*4的方格表,由9种数字组成。其中,每一种数字只会出现在特定的位置,后出现的数字会覆盖之前在当前方格表内出现的。询问当前给出的方格表是否合法。

    注释:输入格式需要注意。

      想法:toposort裸题,我们先预处理出每一个格子可能出现的数字,如果当前数字根本不可能出现在当前格子里,那么就一定是不合法的。如果满足了第一个条件,那么如果当前数字覆盖了本应该在当前格子里出现的数字,我就以当前数字想本应该出现数字之间连一条有向边。然后,不合法的条件就是出现环,因为不可能出现A覆盖B,B又覆盖A的情况。我们在这里采用toposort判环,如果存在一个点没有进队,那么这组数据就是不合法的。

    最后,附上 丑陋的代码... ...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
int cover[110][110][110];//记录当前格子可能出现的数字情况
int tail[110][110];//记录当前格子可能出现的数字个数
bool visit[110];//判断每一个点是否都进过队列
int v[110];//记录每个点的入度
bool map[110][110];//01矩阵,记录两点之间是否存在有向边
int a[110][110];//存储的是当前格子实际存在的数字
using namespace std;
void calc()//预处理每个格子所可能出现的数组(有些麻烦,仅供参考)
{
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
if(i==1||i==4)
{
if(j==1||j==4) tail[i][j]=1;
else tail[i][j]=2;
}
else
{
if(j==1||j==4) tail[i][j]=2;
else tail[i][j]=4;
}
}
}
cover[1][1][1]=1;
cover[1][2][1]=1;cover[1][2][2]=2;
cover[1][3][1]=2;cover[1][3][2]=3;
cover[1][4][1]=3;
cover[2][1][1]=1;cover[2][1][2]=4;
cover[2][2][1]=1;cover[2][2][2]=2;cover[2][2][3]=4;cover[2][2][4]=5;
cover[2][3][1]=2;cover[2][3][2]=3;cover[2][3][3]=5;cover[2][3][4]=6;
cover[2][4][1]=3;cover[2][4][2]=6;
cover[3][1][1]=4;cover[3][1][2]=7;
cover[3][2][1]=4;cover[3][2][2]=5;cover[3][2][3]=7;cover[3][2][4]=8;
cover[3][3][1]=5;cover[3][3][2]=6;cover[3][3][3]=8;cover[3][3][4]=9;
cover[3][4][1]=6;cover[3][4][2]=9;
cover[4][1][1]=7;
cover[4][2][1]=7;cover[4][2][2]=8;
cover[4][3][1]=8;cover[4][3][2]=9;
cover[4][4][1]=9;
}
bool toposort()//裸toposort(拓扑排序)
{
queue<int>q;
while(q.size()) q.pop();
for(int i=1;i<=9;i++)
{
if(!v[i])
{
q.push(i);visit[i]=true;
}
}
while(q.size())
{
int x=q.front();q.pop();
for(int i=1;i<=9;i++)
{
if(map[x][i])
{
v[i]--;
if(v[i]==0)
{
q.push(i);visit[i]=true;
}
}
}
}
for(int i=1;i<=9;i++)//判断数据是否合法
{
if(!visit[i]) return false;
}
return true;
}
void original()//初始化
{
memset(visit,false,sizeof visit);
memset(v,0,sizeof v);
memset(a,0,sizeof a);
memset(map,false,sizeof map);
}
int main()
{
calc();
while(1)
{
original();
char s[100];
scanf("%s",s+1);
int k_k=strlen(s+1);
if(k_k==10) break;
bool flag=false;//临时记录当前数据是否满足第一个条件
bool all=true;//记录所有数据是否都满足第一个条件
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
scanf("%d",&a[i][j]);
flag=false;
for(int len=1;len<=tail[i][j];len++)
{
if(cover[i][j][len]==a[i][j])
{
flag=true;
}
}
if(!flag) all=false;
}
}
for(int i=1;i<=4;i++)//这里是建图的过程
{
for(int j=1;j<=4;j++)
{
for(int k=1;k<=tail[i][j];k++)
{
if(!map[a[i][j]][cover[i][j][k]]&&a[i][j]!=cover[i][j][k])
{
map[a[i][j]][cover[i][j][k]]=1;
v[cover[i][j][k]]++;
}
}
}
}
if(toposort()&&all) printf("THESE WINDOWS ARE CLEAN\n");//如果满足两个条件,数据才是合法的
else printf("THESE WINDOWS ARE BROKEN\n");
scanf("%s",s+1);
}
return 0;
}

    小结:toposort的一个应用,判环。相较于bellmanford的优点就是toposort是O(n),相较于spfa的优点就是没有可以特意hack掉的数据。

最新文章

  1. 【iPhone手机老提示升级怎么办】
  2. js prototype
  3. Maven使用笔记(二)Eclipse中maven项目添加依赖
  4. Codeforce Round #210 Div2
  5. CAN
  6. 解决spring mvc 上传报错,Field [] isn&#39;t an enum value,Failed to convert value of type &#39;java.lang.String[]&#39; to required type &#39;
  7. 用JavaScript获取地址栏参数的方法
  8. 正确理解Python文件读写模式字w+、a+和r+
  9. Alpha第四天
  10. Luogu_2015 二叉苹果树
  11. Linux 常用命令笔记-2
  12. linux7 安装 zlib依赖库 与安装python 3.6
  13. rabbitmq消费端加入精确控频。
  14. SOA、SOAP、RFC、RPC、IETF
  15. springCloud学习之服务注册和发现
  16. ubuntu14.04 cpu-ssd
  17. Linux 建立 TCP 连接的超时时间分析(解惑)
  18. GUI的最终选择Tkinter模块初级篇
  19. ResourceWarning: unclosed &lt;socket.socket fd=864, family=AddressFamily.AF_INET, type=SocketKind.SOCK_STREAM, proto=0, laddr=(&#39;10.100.x.x&#39;, 37321), raddr=(&#39;10.1.x.x&#39;, 8500)&gt;解决办法
  20. Javascript基础之-强制类型转换(二)

热门文章

  1. FindBugs找到错误(一)
  2. Flex中TitleWindow传值
  3. No bean named &#39;cxf&#39; is defined
  4. Html细线表格的实现 打印边框设置
  5. oracle分析函数技术详解(配上开窗函数over())
  6. 获取MySql每一列的数据类型和长度默认值等信息
  7. AI CV 会议2018
  8. sqoop将mysql连表查询结果导入hdfs文件
  9. Linux压缩、解压文件
  10. java.util报错