[POJ][3923][模拟] Ugly Windows

题目大意：

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

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

思路：

2008年北京赛区通过数最高的题目，一道简单的模拟题。只要注意一个窗口完全包含另一个窗口这种情况就好。

代码：

#include
#include
using namespace std;
char map[100][100];
int n,m;
struct point
//用结构体封装每个字母所表示窗口的信息。 
{
    int total;
    //字母出现的次数。 
    int max_x,min_x;
    //字母出现在图中的横坐标的最大值与最小值。 
    int max_y,min_y;
    //字母出现在图中的纵坐标的最大值与最小值。
    bool visit;
    //该字母是否出现过。 
    bool check_edge()
    //判断该字母所表示的窗口的边是否符合顶端窗口要求。 
    {
        if(total!=(max_x-min_x+max_y-min_y)*2)
        //根据字母数量判断窗口是否封闭。 
            return false;
        if(max_x-min_x<2||max_y-min_y<2)
        //判断窗口长宽是否满足>=3的要求。 
            return false;
        //若都满足，返回true。 
        return true;
    }
}letter[26];
void init()
//初始化。 
{
    for(int i=0;i<26;i++)
    {
        letter[i].total=0;
        letter[i].max_x=letter[i].max_y=0;
        letter[i].min_x=letter[i].min_y=100;
        letter[i].visit=false;
    }
}
bool cover(int i,int j)
//判断字母'A'+i所表示的窗口是否在字母'A'+j所表示窗口的内部。 
{
    if(letter[i].max_xletter[j].min_x)
            if(letter[i].max_yletter[j].min_y)
                    return true;
    return false;
}
bool check(int x)
//判断字母'A'+x所表示的窗口是否为顶端窗口。 
{
    if(!letter[x].visit||!letter[x].check_edge())
    //若该字母没被访问过，或其所表示窗口的边不符合要求。 
        return false;
    for(int i=0;i<26;i++)
        if(i!=x&&letter[i].visit&&cover(i,x))
        //若有其它窗口在字母'A'+x所表示的窗口的内部。 
            return false;
    return true;
}
int main()
{
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        init();
        for(int i=0;ij)
                        letter[x].min_x=j;
                    if(letter[x].max_yi)
                        letter[x].min_y=i;
                }
            }
        for(int i=0;i<26;i++)
            if(check(i))
            //若字母'A'+i所表示的窗口为顶端窗口，则输出字母A+i。 
                printf("%c",'A'+i);
        printf("\n");
    }
}

发表回复取消回复