319
poj 2585 Window Pains
格子覆盖问题，有两种方法。
1.可以当做一道模拟题，每次找到一块完整的玻璃，将其取下，看最后能否将所有玻璃取下即可，因为数据量比较少，所以复杂度很低。
2.可以看成一个AOV网络，寻找拓扑排序，看是否存在环，我就这样写的，但是昨晚把topo的dfs写错了o(╯□╰)o，今早查书才发现，dfs的拓扑是从后往前做topo，所以发现已存在在序列中的点是木有影响的。
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#define INF 1E9
using namespace std;
vector<int> map[16];
bool ok[10][10];
int vis[10];
void init()//确定每个点对应的窗口号
{
int i,now=0;
for(i=1;i<10&&now<15;i++)
{
map[now].push_back(i);
map[now+1].push_back(i);
map[now+4].push_back(i);
map[now+5].push_back(i);
now++;
if(i%3==0)now++;
}
return;
}
bool dfs(int m)
{
int i;
vis[m]=-1;
for(i=1;i<10;i++)
{
if(!ok[m][i])continue;
if(vis[i]<0)return 0;//存在环
if(!vis[i]&&!dfs(i))return 0;
}
vis[m]=1;
return 1;
}
bool topo()
{
for(int i=1;i<10;i++)
if(!vis[i]&&!dfs(i))return 0;//增加人为排序
return 1;
}
int main()
{
init();
string s;
int i,t,j;
while(cin>>s&&s!="ENDOFINPUT")
{
memset(vis,0,sizeof(vis));
memset(ok,0,sizeof(ok));
for(i=0;i<16;i++)
{
scanf("%d",&t);
for(j=0;j<map[i].size();j++)
{
if(t==map[i][j])continue;
ok[t][map[i][j]]=1;
}
}
if(topo())cout<<"THESE WINDOWS ARE CLEAN"<<endl;
else cout<<"THESE WINDOWS ARE BROKEN"<<endl;
cin>>s;
}
}
最后更新：2017-04-02 22:14:28