poj2585&&zoj2193 Window Pains ——拓扑排序入门题

April 30, 2013
POJ zoj Graph

题目链接：http://poj.org/problem?id=2585 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2193 题目大意：　　有9个窗口，每个窗口占4个格子，并且每个窗口的位置是固定的。如果重叠的话，在前面的窗口会覆盖另一种窗口，这9个窗口在4*4的矩阵里面，给出一种矩阵的格局。问这中格局是不是合法的。题目思路：　　还是看的书上的。刚开始一点也没有思路。方法就是：16个格子，每个格子可能会存在哪几种窗口，这是可以枚举出来的。针对输入的矩阵，那么可以判断，每一个格子会覆盖哪几种窗口，如果这种窗口在16个格子里面出现过，那么就可以判断当前这个格子一定覆盖了它，那么就可以用一条有向边连接当前窗口和被覆盖的窗口。这样，就可以得到一个图。在16个格子里面没有出现过的窗口我们可以不考虑。得到有向图后，发现，如果存在一个有向环，那么就一定是不合理的，因为这表明，一种窗口A覆盖了另一种窗口B，同时B又覆盖了A，这是不可能的。所以这个矩阵就是不合法的。反之，如果不存在有向环，就是合法的。这样，就转化为用拓扑排序判断环的问题了。先建图，再判断环。写了两遍，其中出现各种BUG…… 第一遍：


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
string cover[4][4];
int a[10][10];bool g[10][10];int id[10];
map<int, bool>mymap;

int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj2585.in", "r", stdin);
#endif
  int i, j, k;
  for (i = 0; i < 4; ++i) for (j = 0; j < 4; ++j)
  cover[i][j].erase();
  for (k = 1; k <= 9; ++k) {
    i = (k - 1) / 3; j = (k - 1) % 3;
    cover[i][j] += (k + '0');
    cover[i][j+1] += (k + '0');
    cover[i+1][j] += (k + '0');
    cover[i+1][j+1] += (k + '0');
  }
  string s; int t = 0;
  while (cin >> s) {
    mymap.clear();
    for (i = 0; i < 10; ++i)
    {
      id[i] = 0;
      for (j= 0; j < 10; ++j)
      {
        g[i][j] = false; a[i][j] = 0;
      }
    } t = 0;
    if (s == "ENDOFINPUT") break;
    for (i = 0; i < 4; ++i) {
      for (j = 0; j < 4; ++j) {
        scanf("%d", &k); a[i][j] = k;
        if (mymap[k] == false) { mymap[k] = true; t++; }
      }
    }
    for (i = 0; i < 4; ++i) {
      for (j = 0; j < 4; ++j) {
        for (int p = 0; p < cover[i][j].length(); ++p) {
          if (g[a[i][j]][cover[i][j][p] -'0'] == false && a[i][j]!=cover[i][j][p] -'0' && mymap[cover[i][j][p]-'0'] ) {
            g[a[i][j]][cover[i][j][p] -'0'] = true; id[cover[i][j][p]-'0' ]++;
          }
        }
      }
    }
    bool flag = true;
    for (i = 0; i < t; ++i) {
      k = 1;
      while (!(mymap[k]&&id[k]==0) && (k <= 9)) k++;
      if (k > 9) {flag = false; break; }
      mymap[k] = false;
      for (j = 1; j <= 9; ++j) {
        if (g[k][j] == true && mymap[j] ) id[j]--;
      }
    }
    if (flag) cout << "THESE WINDOWS ARE CLEAN" << endl;
    else cout << "THESE WINDOWS ARE BROKEN" << endl;
    cin >> s;
  }

  return 0;
}

第二遍：


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
string cover[4][4] = { "1", "12", "23", "3", "14", "1245", "2356", "36",
 "47", "4578", "5689", "69", "7", "78", "89", "9"};
bool edge[10][10];
int a[10][10];
map<int, bool>mymap;
int mystack[10], Count[10];
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj2585.in", "r", stdin);
#endif
  string s; int i, j, k;
  while (cin >> s) {
    if (s == "ENDOFINPUT") break;
    mymap.clear(); memset(edge, false, sizeof(edge));
    int kind = 0;
    for (i = 0; i < 10; ++i) {
      Count[i] = mystack[i] = 0;
    }
    for (i = 0; i < 4; ++i) {
      for (j = 0; j < 4; ++j) {
        scanf("%d", &a[i][j]);
        if (!mymap[a[i][j] ]) {
          mymap[a[i][j] ] = true; kind++;
        }
      }
    }
    for (i = 0; i < 4; ++i) {
      for (j = 0; j < 4; ++j) {
        for (int p = 0; p < cover[i][j].length(); ++p) {
          int nu = cover[i][j][p] - '0';
          if (mymap[nu] &&  edge[a[i][j] ][nu ]==false && nu != a[i][j] ) {
            edge[a[i][j] ][nu] = true; Count[nu]++;
          }
        }
      }
    }
    int top = 0, cnt = 0;
    for (i = 1; i <= 9; ++i) {
      if (Count[i] == 0 && mymap[i]) mystack[++top] = i;
    }
    while (top != 0) {
      int fo = mystack[top]; Count[fo] = -1;
      top--; cnt++;
      for (i = 1; i <= 9; ++i) {
        if (edge[fo][i] == true && mymap[i]) {
          Count[i]--;
        }
      }
      if (!top) // 这个地方，调试很久。不能重复入栈！也就是说，除非栈空了，否则，不要扫描。
      for (i = 1; i <= 9; ++i) {
        if (Count[i] == 0 && mymap[i]) mystack[++top] = i;
      }
    }
    if (cnt < kind) cout << "THESE WINDOWS ARE BROKEN\n";
    else cout << "THESE WINDOWS ARE CLEAN\n";
    cin >> s;
  }

  return 0;
}

细节，很重要。还有，书上的代码貌似有错误……

Read more