设为首页 加入收藏

TOP

HDOJ 4414 Finding crosses 搜索
2012-11-06 11:34:16 来源: 作者: 【 】 浏览:504
Tags:HDOJ  4414  Finding  crosses  搜索

    [cpp]

    //HDOJ 4414 Finding crosses 搜索

    /*

    题意:问一副图中的十字架个数有几个

    十字架的定义是由'#'组成并且十字架的size大于等于3且不能有'#'出现在其相邻的位置(水平、竖直)

    具体请看题目

    思路:枚举中点位置,然后找其四个方向能延伸出去多少个'#',时间复杂度O(n^3)

    */

    #include<stdio.h>

    #include<string.h>

    #include<stdlib.h>

    #define INF 100000000

    #define N 55

    int n;

    char map[N][N];

    bool check(int x,int y){

    if(x >= 0 && x < n && y >=0 && y < n)

    return true;

    return false;

    }

    int Min(int x,int y){

    return x<y x:y;

    }

    bool bx(int x,int y){

    int i,j,xx,yy;

    int a = 1, b = 1, c = 1, d = 1;

    bool aa = false,bb = false,cc=false,dd=false;

    for(i = 1; a == i; ++i){

    yy = y - i;

    if(check(x,yy) && map[x][yy]=='#')

    if(!check(x+1,yy) || (check(x+1,yy)&&map[x+1][yy]!='#'))

    if(!check(x-1,yy) || (check(x-1,yy)&&map[x-1][yy]!='#'))

    ++a;aa=true;

    }

    for(i = 1; b == i ; ++i){

    yy = y + i;

    if(check(x,yy) && map[x][yy]=='#')

    if(!check(x+1,yy) || (check(x+1,yy)&&map[x+1][yy]!='#'))

    if(!check(x-1,yy) || (check(x-1,yy)&&map[x-1][yy]!='#'))

    ++b,bb=true;

    }

    for(i = 1; c == i; ++i){

    xx = x - i;

    if(check(xx,y) && map[xx][y]=='#')

    if(!check(xx,y+1) || (check(xx,y+1)&&map[xx][y+1]!='#'))

    if(!check(xx,y-1) || (check(xx,y-1)&&map[xx][y-1]!='#'))

    ++c,cc=true;

    }

    for(i = 1; d == i; ++i){

    xx = x + i;

    if(check(xx,y) && map[xx][y]=='#')

    if(!check(xx,y+1) || (check(xx,y+1)&&map[xx][y+1]!='#'))

    if(!check(xx,y-1) || (check(xx,y-1)&&map[xx][y-1]!='#'))

    ++d,dd=true;

    }

    return a==b && b==c && c==d && aa && bb && cc && dd;

    }

    int cal(){

    int i,j,ans = 0;

    for(i = 0; i < n; ++i){

    for(j = 0; j < n; ++j)

    if(map[i][j] == '#' && bx(i,j))

    ++ans;

    }

    return ans;

    }

    int main(){

    int i;

    while(scanf("%d",&n),n){

    for(i = 0; i < n; ++i)

    scanf("%s",map[i]);

    printf("%d\n",cal());

    }

    return 0;

    }

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇C++学习指针一二事 下一篇hdu 4417 2012杭州网络..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: