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