[POJ 2585] Window Pains 拓朴排序

冷不防 2023-10-11 09:34 73阅读 0赞

题意：你现在有9个2\*2的窗口在4\*4的屏幕上面，由于这9这小窗口叠放顺序不固定，所以在4\*4屏幕上有些窗口只会露出来一部分。

如果电脑坏了的话，那么那个屏幕上的各小窗口叠放会出现错误。你的任务就是判断一下这个电脑到底坏了没有。

![1633695-20190911170636910-935093568.png][]

题解：

要注意1.2.3....9这几个窗口的位置是不变的，它只会被其他窗口挡住

刚开始我想的是，让这9个窗口叠放的顺序枚举一下，记录下来它最后的结果（结果也就9!个）。然后对每一次输入找一下这里面有没有这个结果。

但是感觉这个太麻烦了！！！

还可以使用拓扑排序，对每一个窗口的位置进行枚举，如果这4个位置上面的值与此时窗口的标号不同，那就证明这几个窗口叠放顺序要在它之后。就建一条边。

假设这个是1窗口，那么它的四个位置上面应该都是1，如果出现了2或者3等等，那就证明2或者3等等窗口叠放顺序在1窗口之后。那就给1建一条从1到2或者3等等窗口的边。这就表明了在这种叠放顺序中只有让2或者3等等窗口拿走后1窗口才会全部展现出来

输入中肯定有至少一个窗口的所有位置都没有被其他窗口占用，那么拓扑排序就从这里开始。就把这个窗口拿走还要把与这个窗口的边也取消掉

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<vector>
     6 #include<queue>
     7 using namespace std;
     8 const int maxn=10;
     9 int mp[5][5],quality[maxn],link[10][10];
    10 char s[2*maxn];
    11 bool check()
    12 {
    13     for(int i=1;i<=9;++i)
    14     {
    15         if(quality[i]>0)
    16         {
    17             return false;
    18         }
    19     }
    20     return true;
    21 }
    22 int main()
    23 {
    24     while(~scanf("%s",s))
    25     {
    26 
    27         if(strcmp(s,"START")==0)
    28         {
    29             memset(quality,0,sizeof(quality));
    30             memset(link,0,sizeof(link));
    31             for(int i=1;i<=4;++i)
    32             {
    33                 for(int j=1;j<=4;++j)
    34                 {
    35                     scanf("%d",&mp[i][j]);
    36                 }
    37             }
    38             scanf("%s",s);
    39             int cnt=0;
    40             for(int i=0;i<=2;++i)
    41             {
    42                 for(int j=0;j<=2;++j)
    43                 {
    44                     cnt++;
    45                     //printf("%d\n",cnt);
    46                     for(int ii=i+1;ii<=i+2;++ii)
    47                     {
    48                         for(int jj=j+1;jj<=j+2;++jj)
    49                         {
    50                             int u=mp[ii][jj];
    51                             if(u!=cnt)
    52                             {
    53                                 link[cnt][u]++;
    54                                 quality[cnt]++;
    55                             }
    56                         }
    57                     }
    58                 }
    59             }
    60             queue<int>r;
    61             while(!r.empty()) r.pop();
    62             for(int i=1;i<=9;++i)
    63             {
    64                 if(quality[i]==0)
    65                 {
    66                     r.push(i);
    67                     quality[i]=-1;
    68                 }
    69             }
    70             while(!r.empty())
    71             {
    72 
    73                 int x=r.front();
    74                 r.pop();
    75                 for(int i=1;i<=9;++i)
    76                 {
    77                     if(i==x) continue;
    78                     if(link[i][x])
    79                     {
    80                         //printf("%d %d %d %d\n",x,i,quality[i],link[i][x]);
    81                         quality[i]-=link[i][x];
    82                         link[i][x]=0;
    83                         if(quality[i]==0)
    84                         {
    85                             quality[i]=-1;
    86                             r.push(i);
    87                         }
    88                     }
    89                 }
    90             }
    91             if(check())
    92                 printf("THESE WINDOWS ARE CLEAN\n");
    93             else printf("THESE WINDOWS ARE BROKEN\n");
    94         }
    95         else break;
    96     }
    97     return 0;
    98 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11507533.html

[1633695-20190911170636910-935093568.png]: https://img2018.cnblogs.com/blog/1633695/201909/1633695-20190911170636910-935093568.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif