首页 > 代码库 > Ugly Windows

Ugly Windows

2024-07-15 10:09:51   225人阅读

poj3923:http://poj.org/problem?id=3923

题意：给出两个整数n、m表示屏幕的长宽。屏幕上有一些窗口，每个窗口都是矩形的，窗口的边框用同一个大写字母来表示，不同的窗口的大写字母必定不同。

由于窗口的重叠，有些窗口的有些部分被其他窗口覆盖。但是，肯定有一些窗口在最顶端，不被其他任何窗口覆盖。我们称这些窗口为“顶端窗口”。你的任务就是找出所有的顶端窗口。

题解：简单的模拟。结果我错了很多次啊。首先，没有考虑到边框的内部一定要是‘.‘，然后是最坑就是每个窗口的高度和宽度都不能小于3，自己模拟能力还是很弱啊，要多打打。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 bool visit[30],ans[30]; 8 char mp[102][102]; 9 struct Node{10    int x1,y1;11    int x2,y2;12 }num[30];13 int n,m;14 int main(){15     while(~scanf("%d%d",&n,&m)){16         if(n==0&&m==0)break;17         if(n<3||m<3)continue;18         memset(visit,0,sizeof(visit));19         memset(num,0,sizeof(num));20         memset(mp,0,sizeof(mp));21         memset(ans,0,sizeof(ans));22         for(int i=0;i<=29;i++){23             num[i].x1=num[i].y1=1000;24             num[i].x2=num[i].y2=0;25         }26         for(int i=1;i<=n;i++)27             for(int j=1;j<=m;j++){28                 cin>>mp[i][j];29                 if(mp[i][j]!=‘.‘){30                     num[mp[i][j]-‘A‘].x1=min(num[mp[i][j]-‘A‘].x1,i);31                     num[mp[i][j]-‘A‘].y1=min(num[mp[i][j]-‘A‘].y1,j);32                     num[mp[i][j]-‘A‘].x2=max(num[mp[i][j]-‘A‘].x2,i);33                     num[mp[i][j]-‘A‘].y2=max(num[mp[i][j]-‘A‘].y2,j);34                     visit[mp[i][j]-‘A‘]=1;35                 }36             }37         for(int i=0;i<=29;i++){38             if(visit[i]){39                 int t1=num[i].x1;40                 int t2=num[i].y1;41                 int t3=num[i].x2;42                 int t4=num[i].y2;43                 bool flag=false;44                for(int j=t2;j<=t4;j++){45                  if((mp[t1][j]!=(‘A‘+i))||(mp[t3][j]!=(‘A‘+i))){46                     flag=true;47                     break;48                  }49                }50                 for(int j=t1;j<=t3;j++){51                  if(mp[j][t2]!=(‘A‘+i)||mp[j][t4]!=(‘A‘+i)){52                     flag=true;53                     break;54                  }55                }56                if(t3-t1<2||t4-t2<2)flag=true;57             if(!flag)58               ans[i]=1;59             }60         }61         for(int i=0;i<=29;i++){62            if(visit[i]){63               for(int k=num[i].x1+1;k<num[i].x2;k++){64                 for(int j=num[i].y1+1;j<num[i].y2;j++){65                     if(mp[k][j]!=‘.‘)66                         ans[i]=0;67                 }68               }69            }70         }71         for(int i=0;i<=29;i++)72             if(ans[i])73             printf("%c",i+‘A‘);74        printf("\n");75     }76 }
View Code

 


联系
我们