首页 > 代码库 > POJ 1856 Sea Battle(BFS).
POJ 1856 Sea Battle(BFS).
~~~~
题意: 给你一个R*C的图,求其由图中连通‘#“所组成的矩形的个数。
注意:If the shipswere placed correctly (i.e., there are only rectangles that do not touch each other even with a corner), print the sentence "There are S ships." where S is the number of ships. Otherwise, print the sentence "Bad placement.".
所以若有一组连通的’#‘不能组成矩形,则输出 Bad placement。
题目链接:http://poj.org/problem?id=1856
~~~~
思路:对每个’#‘进行DFS,求其’#‘的个数s(就是面积)。DFS同时,记录y可以搜到的最左和最右位置,记录x可以搜到的最上和最下位置。
则若 s==(r-l+1)*(u-d+1),则 tot++..
~~~~
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<string> #include<queue> #define N 1111 using namespace std; int tot,n,m; int s,l,r,u,d; char g[N][N]; bool ok(int x,int y) { return (x>=0 && x<n && y>=0 && y<m && g[x][y]=='#'); } void dfs(int x,int y) { s++; l=min(y,l); u=min(u,x); r=max(y,r); d=max(d,x); g[x][y]='.'; for(int i=-1;i<=1;i++) //八个方向进行搜索。 for(int j=-1;j<=1;j++) if(ok(x+i,y+j)) dfs(x+i,y+j); return ; } int main() { while(scanf("%d%d",&n,&m)==2) { if(n==0 && m==0) break; for(int i=0;i<n;i++) scanf("%s",g[i]); int tot=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(g[i][j]=='#') { s=0; l=r=j; u=d=i; dfs(i,j); if(s==(r-l+1)*(d-u+1)) tot++; else i=n,j=m,tot=-1; //跳出循环。 } } } if(tot<0) printf("Bad placement.\n"); else printf("There are %d ships.\n",tot); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。