題目鏈接：HDU 4414 Finding crosses

【題目大意】

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

十字架的縱向長(zhǎng)度等于橫向長(zhǎng)度 ， 且這個(gè)長(zhǎng)度要為大于等于3的奇數(shù)。

構(gòu)成十字架的#周圍不能有多余的#

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

【解法】

對(duì)每個(gè)有#元素的位置bfs ， 一層一層的擴(kuò)展，每次擴(kuò)展檢測(cè)周圍是否有多余的#，沒(méi)有就繼續(xù)擴(kuò)展， 有就返回0，不能擴(kuò)展了就判斷是否為合格的十字架。

【源代碼】

#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， 實(shí)現(xiàn)一層層擴(kuò)展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;不能擴(kuò)展了就跳出循環(huán)if(step != 4) //說(shuō)明沒(méi)有完全擴(kuò)展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; }

轉(zhuǎn)載于:https://www.cnblogs.com/chaiwenjun000/p/5321164.html

總結(jié)

以上是生活随笔為你收集整理的HDU 4414 Finding crosses（搜索）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。