JDOJ1740 卫星照片Satel


JDOJ1740

农夫 John 正在研究他的农场的卫星照片.照片为一个R (1 <=R <= 75) 行 C (1 <= C <= 75) 列的字符矩阵表示.如下图:
..................
..#####.......##..
..#####......##...
..................
#.......###.....#.
#.....#####.......
图上的一块相连通的 "#" 表示一群奶牛或一个房间, 两个子"#" 连通的意思是说左右或上下相连.而下面的两块则是分开的:
....
.#..
..#.
....
John现在根据卫星照片上的的这些"#"块的形状来判断哪些是牛群,哪些是房间.如果一个"#"块形状的边是水平或垂直的矩形,则是房间.其它的则认为都是牛群.在第一个图中,有三个房间 ( 2x1, 2x5, and 1x1)和2群牛.
请根据输入文件中的数据,统计出房间数和牛群数.

数据中牛群不会包围另一个牛群或房间.


这道题不说是DFS/BFS看数据范围和地图也可以发现是搜索的题……那么,这道题究竟如何写呢?

本题的目的,就是去判断地图中标准矩形的存在。DFS可以解决这样的问题(不然数据范围也不会这么小)

所以就上DFS咯~

如何判断标准矩形呢?


Ⅰ:Color染色

我们可以将整个图转化为一个bool型二位数组dfsmap[][],之后再建立一个bool二维数组newmap[][],每次DFS从dfsmap中一个被标记的点开始进行,标记在newmap上,之后对newmap[][]进行判断矩形操作。

如何判断矩形呢?

DFS的外部循环保证了DFS的起始点一定是某个图形的左上角的点。那么我们就从右上角开始向右延伸,取消延伸到的标记,此时我们有y,x1->x2表示newmap上(x1,y)~(x2,y)已经被标记了。

那么我们再向下标记,对满足newmap[x1][i]的i扫map[x1~x2][i],这样的话就可以取消所有newmap里的标记。

如果在去除标记时发现有的地方没被染色(!newmap[][])即视为不是矩形。

待扫完矩形区域之后再扫一遍整张地图看看是否全部取消标记了,如果有的地方还没取消标记说明这个这个点所在区域不是一个完整的矩形。

是一个可行方案。可是还能优化吗?


Ⅱ.扩展与扫描

我曾经的想法是先进行DFS之后判断。我们可不可以直接先进行判断,之后再DFS呢?

What?

先扫入建立dfsmap[][],之后进行遍历,如果发现有一个点是图形的一部分而且没有被扫过那么就开始从那点向右向下扩展,之后我们会得到一个边界(一个最大的x和一个最大的y)(仅基于对左上角点向右向下延伸的结果),之后进行DFS,每到一个点就判断它是否超出了我们所规定的边界或者存在一个点不是图形中的一部分但是却在所确定的范围内。


第一种方法并没有写完,所以并没有测试……(似乎样例都过不去哇QwQ)

第二种写完之后各种RE,我的内心已经基本是崩溃的了……

在进行多方求助和咨询之后,我找到了自己代码中的两个问题并加以修复……看来果然不是我的思路出现了问题是我的代码实现……


问题1:

return a&&b; //a and b have the type of bool.

这是一个看起来十分简单的bool型函数返回语句,意思是当a成立且b成立时返回true,其他情况下均返回false。

当这个东西变成这样:return a && f(x);

仍然没什么,蛤~依旧当a和f(x)的返回值均为true时返回true,其他时候返回false。

但是事实上,&&,||运算符是有这样的法则的:当从前往后执行时遇到了一个值使得整个式子的结果固定(即后面的式子即使运行也不会对最终结果产生影响),那么就会停止判断下面的式子

当我们f(x)只是进行一些check()工作,即只读取不写入的工作的话呢,当然是可以的啦~但是如果我们进行的是dfs()这样的函数,那么就不一样了……

此时将会放弃对f(x)的运行,这种运算符被称作“短路运算符”,而这个东西设计出来的初衷是为了加快代码运行速度#翻白眼,而不是卡你……

当然数据会有单独卡这种东西的啦~


问题2

千万不要用%c读入字符!

这样读入在Windows和Linux下产生的效果是不同的,似乎是UTF-8和GBK的锅?还是g++的锅?我们不得而知。但是以后在需要读入字符串进行处理的时候,请一定要按行读入,否则因为换行符的不同和字符集的不同就会导致读不进来图,读进来的图是错的等情况#无奈脸


#include <cstdio>
#include <cstring>
#include <algorithm>
 
char tmp[100];
int r,c,farmans,cowans,dira[]={1,-1,0,0},dirb[]={0,0,1,-1};
bool map[80][80],use[80][80];
 
bool dfs(int a,int b,int edgex1,int edgey1,int edgex2,int edgey2)
{
    bool flg=true;
    use[a][b]=true;
    for(int i=0;i<4;++i)
    {
        int newx=a+dira[i],newy=b+dirb[i];
        if(newx<=0||newx>r||newy<=0||newy>c)  continue;
        if(use[newx][newy])  continue;
        if(newx>edgex2||newx<edgex1||newy>edgey2||newy<edgey1)
        {
            if(map[newx][newy])
            {
                flg=false;
                dfs(newx,newy,edgex1,edgey1,edgex2,edgey2);
            }
        }
        else
        {
            if(!map[newx][newy])
            {
                flg=false;
                continue;
            }
            bool tmp=dfs(newx,newy,edgex1,edgey1,edgex2,edgey2);
            flg=tmp&&flg;
        }
    }
    return flg;
}
 
void init(int a,int b)
{
    int x,y;
    for(y=b;map[a][y];++y);
    --y;
    for(x=a;map[x][b];++x);
    --x;
    if(dfs(a,b,a,b,x,y)) farmans++;
    else cowans++;
    return;
}
 
int main()
{
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;++i)
    {
        scanf("%s",tmp);
        for(int j=0;j<c;++j) map[i][j+1]=(tmp[j]=='#')?true:false;
    }
    for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j)
            if(map[i][j]&&!use[i][j]) init(i,j);
    printf("%d\n%d",farmans,cowans);
    return 0;
}

写在最后

想切好OI题,不仅要有过硬的审题能力以及算法技能,同时还要有过硬的代码能力和一些技巧。这就需要我们多做题, 多见题,提高代码能力的同时掌握一些其他技能#滑稽,还需要多多总结,这样才能取得成功。

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - JDOJ1740 卫星照片Satel


不骗了,不骗了。
A Simple OIer fighting tooth and nail.