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;   www.2cto.com
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; 
}