HDU 4414 Finding crosses（搜索）

題目鏈接：HDU 4414 Finding crosses

【題目大意】

給你一張n*n的圖，由o #這兩個元素組成，讓我們找其中有多少十字架。 十字架由#構成

十字架的縱向長度等于橫向長度 ， 且這個長度要為大于等于3的奇數。

構成十字架的#周圍不能有多余的#

如圖1滿足條件， 圖二不滿足，圖三不滿足，圖四不滿足， 這三個不滿足的條件都是有了多余的#；

【解法】

對每個有#元素的位置bfs ， 一層一層的擴展，每次擴展檢測周圍是否有多余的#，沒有就繼續擴展， 有就返回0，不能擴展了就判斷是否為合格的十字架。

【源代碼】

#include <iostream>
#include <cstdio>
using namespace std;
char map[55][55];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};int n;
bool bfs(int a,int b){int ans = 0;int cnt = 0;for(int i=1;i<=25;i++){int step = 0;for(int j=0;j<4;j++){int nx = a+dx[j]*i; //*i， 實現一層層擴展int ny = b+dy[j]*i;if(nx<0 || nx>=n|| ny<0|| ny>=n) continue;if(map[nx][ny] == '#'){step++;if(j==2 || j==3){if(ny>0 && map[nx][ny-1] == '#' || ny<n-1 &&map[nx][ny+1]=='#') //判斷相鄰的位置是否有 #return false;}else{if(nx>0 && map[nx-1][ny] == '#' || nx<n-1 &&map[nx+1][ny]=='#') //判斷相鄰的位置是否有 #return false;}cnt++;}}if(step == 0) break;不能擴展了就跳出循環if(step != 4) //說明沒有完全擴展return false;}if(cnt%2==0&& cnt>0)return true;elsereturn false;
}
int main(){while(scanf("%d",&n)!=EOF && n){for(int i=0;i<n;i++){for(int j=0;j<n;j++){scanf(" %c",&map[i][j]);}}int ans = 0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(map[i][j] == '#'){ans+= bfs(i,j);}}}printf("%d\n",ans);}return 0;
}