POJ 2585 Window Pains题解

POJ 2585 Window Pains题解

题目链接：2585 -- Window Pains (poj.org)

题目描述：

就不翻译了，可以自己打开链接去百度翻译。

---

解题思路：

因为9个窗口大部分都可以同时存在几个程序。所以最上面的程序一定是把另外几个遮住了。所以先写出各个格子可能的程序窗口编号的表格（下图），然后根据这个表格对输入进行构图：

例：如果A遮住了B和C，那么A->B,A->C。

构出有向图后，用拓扑排序判断有无环路，有环路则计算机死机。

 那么比如第一个例题：

 

 

构造出来的有向图就是：

 

再通过拓扑排序判断有无回路即可。

这道题建图有点烦的，后面都还好。本来最开始想用链式前向星写，后来改成邻接矩阵了。

---

AC代码： 

#include
#include
#include
#include
#include
using namespace std;
const int INF = 0x3f;
const int MAX_N = 20;
//____________邻接矩阵__________
int map[10][10];
//____________AOV_______________
int d[MAX_N];//保存入度
int vis[MAX_N];
queueq;//保存入度为0的顶点
//______________________________
int num[5][5];
string rule[5][5];


//初始化
inline void init(){
    memset(map,0,sizeof(map));
    memset(d,0,sizeof(d));
    memset(vis,0,sizeof(vis));
    while(!q.empty()) q.pop();//清空队列
}

int AOV(int n){
    int all = 0;//用于判断环路
    //找入度为0的点
    for(int i = 1;i<=n;i++){
        if(d[i] == 0){
            q.push(i);
            vis[i] = 1;
        }
    }
    //开始计算
    while(!q.empty()){
        int u = q.front();
        q.pop();
        all++;
        for(int v = 1;v<=n;v++){
            if(map[u][v] == 1) d[v]--;
            map[u][v] = 0;
            if(d[v] == 0&&!vis[v]){
                q.push(v);
                vis[v] = 1;
            }
        }
    }
    if(all == n) return 1;
    return 0; 
}

inline void get_rule(){
    rule[1][1] = "1";rule[1][2] = "12";rule[1][3] = "23";rule[1][4] = "3";
    rule[2][1] = "14";rule[2][2] = "1245";rule[2][3] = "2356";rule[2][4] = "36";
    rule[3][1] = "47";rule[3][2] = "4578";rule[3][3] = "5689";rule[3][4] = "69";
    rule[4][1] = "7";rule[4][2] = "78";rule[4][3] = "89";rule[4][4] = "9";
}

inline void get_map(int n){
    for(int i = 1;i<=4;i++){
        for(int j = 1;j<=4;j++){
            for(int k = 0;rule[i][j][k];k++){
                if(num[i][j]+'0' == rule[i][j][k]) continue;
                else map[num[i][j]][rule[i][j][k]-'0'] = 1;
            }
        }
    }
    //得到入度
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            if(map[j][i] == 1) d[i] ++;
        }
    }
}

inline void print_map(int n){
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++) 
            cout<>op && op!="ENDOFINPUT"){
        init();
        for(int i = 1;i<=4;i++)
            for(int j = 1;j<=4;j++)
                cin>>num[i][j];
        cin>>op;
        get_map(9);
        // print_map(9);
        if(AOV(9)) cout<<"THESE WINDOWS ARE CLEAN"< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714249.html