WUST 2090 HLD与停车场（bfs||dfs||暴力模拟||巧妙思维）

超、凢脫俗 2022-06-05 11:45 175阅读 0赞

## 2090: HLD与停车场 ##

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld  
Submitted: 21 Accepted: 6  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

HLD最近迷上了保加利亚妖王，这天他打算去河北省参加保加利亚妖王的演唱会，但是很不幸他被保加利亚妖王的死对头比利王的手下王大锤抓住了。

由于和王大锤一起执行任务的龙卷风这天生病请假了，王大锤给HLD布置了一个任务，如果能完成这个任务就放他走，否则就会带回去和比利王搞一辈子比利emmmmm，无奈之下HLD只能接下了这个任务--------龙卷风摧毁停车场。

## Input ##

王大锤会告诉HLD两个数字n，m，分别代表地图的长和宽（2<=n<=20,2<=m<=20），会给HLD一张n\*m的图，”.”代表路，”\*”号代表停车场的边缘（图只包含这两个字符）

任意两个停车场不相邻，停车场都是完整的矩形，（可以看样例了解一下），然后给一个要求摧毁的数字x（x<100），保证任意停车场的边长不小于2，数据为多组输入。

## Output ##

现在让HLD在摧毁所有停车场后写一份摧毁报告，如果达到了要求就写上：”乌鸦坐飞机”，否则写”boy next door!”（均不包括引号）

现在HLD一股脑把所有的停车场摧毁了，但是忘记记录下来了，你能告诉他他应该写下什么吗？

## Sample Input ![copy.gif][] ##

3 6
    ..***.
    ..*.*.
    ..***.
    1
    5 6
    ..**..
    ..**..
    ......
    ***...
    ***...
    3

## Sample Output ##

乌鸦坐飞机
    boy next door!

## HINT ##

样例一给出的图中有一个停车场

样例二中有两个停车场

比如可能会出现：

\*\*

也表示一个停车场

\*\*\*\*

\*..\*

\*\*\*\*

也表示一个停车场

## Author ##

hjy

\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

题解：

第一次出题，新生杯比赛的时候一小时都没人尝试，然后加了一组样例和hint解释以后就有人a了。。感觉不是很难啊，我分配的是出简单题的qwq

思路：

这题的做法很多，可以二重循环遍历图，遇到星号就矩形数加一，暴力分别扫上边，左边，下边和右边，扫到了星号就消掉，这里考察模拟能力，然后更高级一些的解法可以bfs和dfs，巧妙的做法是二重循环遍历图，遇到星号判断它的左边和上边，如果都是点或者边界那就矩形数加一

标程：

#include<stdio.h>
    int judge(char s[][25],int x,int y)
    {
        if((x-1<0||s[x-1][y]=='.')&&(y-1<0||s[x][y-1]=='.'))
            return 1;
        return 0;
    }
    int main()
    {
        //freopen("datain.txt","r",stdin);
        //freopen("dataout.txt","w",stdout);
        char s[25][25];
        int n,m,i,j,a,b,d,ans;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            ans=0;
            for(i=0;i<n;i++)
                scanf("%s",s[i]);
            scanf("%d",&d);
            for(i=0;i<n-1;i++)
            {
                for(j=0;j<m-1;j++)
                {
                    if(s[i][j]=='*'&&judge(s,i,j))
                    {
                        ans++;
                    }
                }
            }
            if(ans>=d)
                printf("乌鸦坐飞机\n");
            else
                printf("boy next door!\n");
        }
       return 0;
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=2090&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=2090&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=2090&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif