首页 > 代码库 > POJ 1856 Sea Battle
POJ 1856 Sea Battle
题意:找出R*C的图中不想交的矩形个数,如果有一个相交矩形就输出Bad placement. 不然就输出能放多少船
不相交是说对于一个矩形(‘#’组成)周围一圈都是由‘.’包围,所以我们只用求出以某个点为起点的最大和最小的x,y的值,并且在搜索时‘#’的个数rec,如果rec=(maxx-minx+1)*(maxy-miny+1)成立,则这个矩形合法
#include <iostream> #include<stdio.h> #include<string> #include<cstring> #include<algorithm> #include<cmath> #define N 1010 int maxx,maxy,minx,miny; using namespace std; char map[N][N]; int r,c; bool check(int x,int y) { if(x>=0&&x<r&&y>=0&&y<c&&map[x][y]=='#') return true; return false; } int dfs(int x,int y) { minx=min(minx,x); maxx=max(maxx,x); miny=min(miny,y); maxy=max(maxy,y); map[x][y]='.'; int rec=1; for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++) { if(check(i+x,j+y)) { rec+=dfs(i+x,j+y); } } return rec; } int main() { while(~scanf("%d%d",&r,&c)) { if(r==0&&c==0) break; for(int i=0;i<r;i++) scanf("%s",map[i]); int ans=0; for(int i=0;i<r;i++) for(int j=0;j<c;j++) { if(map[i][j]=='#') { maxx=minx=i; maxy=miny=j; int rec=dfs(i,j); if(rec==(maxx-minx+1)*(maxy-miny+1)) ans++; else { ans=-1;//只要有一艘坏船就是bad i=r; break; } } } if(ans==-1) printf("Bad placement.\n"); else printf("There are %d ships.\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。