POJ 2585 Window Pains 题解

链接：http://poj.org/problem?id=2585

题意：

　　某个人有一个屏幕大小为4*4的电脑，他很喜欢打开窗口，他肯定打开9个窗口，每个窗口大小2*2。并且每个窗口肯定在固定的位置上(见题目上的图)，某些窗口可以覆盖另一些窗口(可以脑补)。询问给出的电脑屏幕是否是合法的。

分析：

　　可以预先处理出每个格子应该有哪几个窗口在这上面，将最上面的窗口与其他窗口连边，得到一张图，用拓扑判环，因为这道题太简单了，所以我就写这么短的题解。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
int a[5][5];
queue <int> que;
vector<int> table[5][5];
vector <int> g[20];

int main(){
  for(int i=1;i<=9;i++){
    int x=ceil((double)i/3.0);
    int y=i%3;if(!y)y=3;
    table[x][y].push_back(i);
    table[x+1][y].push_back(i);
    table[x][y+1].push_back(i);
    table[x+1][y+1].push_back(i);
  }//预处理出每个格子应当有的窗口
  string str;
  while(cin >> str){
    int siz[20];
    int num=0;
    memset(siz,0,sizeof(siz));
    for(int i=1;i<=9;i++) g[i].clear();
    if(str=="ENDOFINPUT")return 0;
    memset(a,0,sizeof(a));
    for(int i=1;i<=4;i++){
      for(int j=1;j<=4;j++){
    cin>>a[i][j];
      }
    }
    for(int i=1;i<=4;i++){
      for(int j=1;j<=4;j++){
    for(int k=0;k<table[i][j].size();k++){
      if(table[i][j][k]==a[i][j])continue;
      g[a[i][j]].push_back(table[i][j][k]);//连边
      siz[table[i][j][k]]++;
    }
      }
    }
    for(int i=1;i<10;i++){
      if(!siz[i])que.push(i);
    }
    while(!que.empty()){//topu判环
      int k=que.front();
      que.pop();
      num++;
      for(int i=0;i<g[k].size();i++){
    siz[g[k][i]]--;
    if(!siz[g[k][i]])que.push(g[k][i]);
      }
    }
    if(num==9){
      cout<<"THESE WINDOWS ARE CLEAN
";
    }else cout<<"THESE WINDOWS ARE BROKEN
";
    string str;
    cin >> str;
  }
}