本文主要是介绍zoj 2193 poj 2585 Window Pains，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给定屏幕当前的状态，判断屏幕是否显示正常。其实就是把“覆盖”当做一条有向边，建图之后判断该图是否存在环。
思路：先建图，然后进行拓扑排序。这题建图是关键，每一个窗口有一个自己的区域，若区域a上是窗口b，则说明窗口a被窗口b覆盖，则存在一条有向边b->a，扫描9个区域之后则将所有的边添加完毕，不过会存在重复的边，将其去掉后即可。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>using namespace std;const int maxn = 10;int screen[4][4];
vector<int> list[maxn]; //邻接表
int ind[maxn]; //入度 bool Input(){string s;cin>>s;if(s == "ENDOFINPUT") return false;for(int i = 0; i < 4; i++){for(int j = 0; j < 4; j++)cin>>screen[i][j];}cin>>s;return true;
}void Build(){for(int i = 1; i <= 9; i++) {list[i].clear(); ind[i] = 0;}for(int k = 1; k <= 9; k++){//第k个窗口 int i = (k-1)/3;int j = (k-1)%3;if(screen[i][j] != k) list[screen[i][j]].push_back(k);if(screen[i][j+1] != k) list[screen[i][j+1]].push_back(k);if(screen[i+1][j] != k) list[screen[i+1][j]].push_back(k);if(screen[i+1][j+1] != k) list[screen[i+1][j+1]].push_back(k);}for(int i = 1; i <= 9; i++){//去除重复的边 list[i].erase(unique(list[i].begin(),list[i].end()),list[i].end());}for(int i = 1; i <= 9; i++){//统计入度 for(int j = 0; j < list[i].size(); j++){ind[list[i][j]]++;}}}bool TopSort(){stack<int> st;for(int i = 1; i <= 9; i++){if(ind[i] == 0) st.push(i);}for(int i = 0; i < 9; i++){if(st.empty()) return false;int u = st.top(); st.pop();for(int j = 0; j < list[u].size(); j++){int v = list[u][j];if(--ind[v] == 0) st.push(v);}}//end of forreturn true;
}void Solve(){Build();printf("THESE WINDOWS ARE %s\n",TopSort()?"CLEAN":"BROKEN");
}int main(){while(Input()){Solve();}return 0;
}这篇关于zoj 2193 poj 2585 Window Pains的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
