延边延吉网站建设,做噯噯的网站,服装 营销型网站案例,网站建设推广群题目链接#xff1a;HDU 4414 Finding crosses 【题目大意】 给你一张n*n的图#xff0c;由o #这两个元素组成#xff0c;让我们找其中有多少十字架。 十字架由#构成 十字架的纵向长度等于横向长度 #xff0c; 且这个长度要为大于等于3的奇数。 构成十字架的#周围不能有多… 题目链接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 i1;i25;i){int step 0;for(int j0;j4;j){int nx adx[j]*i; //*i 实现一层层扩展int ny bdy[j]*i;if(nx0 || nxn|| ny0|| nyn) continue;if(map[nx][ny] #){step;if(j2 || j3){if(ny0 map[nx][ny-1] # || nyn-1 map[nx][ny1]#) //判断相邻的位置是否有 #return false;}else{if(nx0 map[nx-1][ny] # || nxn-1 map[nx1][ny]#) //判断相邻的位置是否有 #return false;}cnt;}}if(step 0) break;不能扩展了就跳出循环if(step ! 4) //说明没有完全扩展return false;}if(cnt%20 cnt0)return true;elsereturn false;
}
int main(){while(scanf(%d,n)!EOF n){for(int i0;in;i){for(int j0;jn;j){scanf( %c,map[i][j]);}}int ans 0;for(int i0;in;i){for(int j0;jn;j){if(map[i][j] #){ans bfs(i,j);}}}printf(%d\n,ans);}return 0;
}转载于:https://www.cnblogs.com/chaiwenjun000/p/5321164.html
