首页 > 代码库 > poj1856Sea Battle(DFS)
poj1856Sea Battle(DFS)
题目链接:
huangjing
思路:
这个题目当时想到是找联通快,但是不知道怎么判断这个联通快是不是标准的好船,后来看了别人的题解才知道可以用面积去判断。。。这个知道了就是简单的dfs找联通快了。。注意是如果出现一艘破船则不用找了,直接输出就可以了。。。
题目:
Sea Battle
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 2809 | Accepted: 996 |
Description
During the Summit, the armed forces will be highly active. The police will monitor Prague streets, the army will guard buildings, the Czech air space will be full of American F-16s. Moreover, the ships and battle cruisers will be sent to guard the banks of the Vltava river. Unfortunately, in the case of any incident, the Czech Admiralty have only a few captains able to control over the large sea battle. Therefore, it was decided to educate new admirals. As an excellent preparation, the game of "Sea Battle" was chosen to help with their study program.
In this well-known game, a predefined number of ships of predefined shapes are placed on the square board in such a way that they cannot contact one another even with their corners. In this task, we will consider rectangular shaped ships only. The unknown number of rectangular ships of unknown sizes are placed on a rectangular board. All the ships are full rectangles built of hash characters. Write a program that counts the total number of ships present in the field.
In this well-known game, a predefined number of ships of predefined shapes are placed on the square board in such a way that they cannot contact one another even with their corners. In this task, we will consider rectangular shaped ships only. The unknown number of rectangular ships of unknown sizes are placed on a rectangular board. All the ships are full rectangles built of hash characters. Write a program that counts the total number of ships present in the field.
Input
The input consists of more scenarios. The description of each scenario begins with two integer numbers R and C separated with a single space, 1 <= R,C <= 1000. These numbers give the number of rows and columns in the game field.
After these two numbers, there are R lines, each of them containing C characters. Each character is either hash ("#") or dot ("."). Hashes denote ships, dots water.
Then, the next scenario description begins. At the end of the input, there will be a line containing two zeros instead of the field size.
After these two numbers, there are R lines, each of them containing C characters. Each character is either hash ("#") or dot ("."). Hashes denote ships, dots water.
Then, the next scenario description begins. At the end of the input, there will be a line containing two zeros instead of the field size.
Output
Output a single line for every scenario. If the ships were 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.".
Otherwise, print the sentence "Bad placement.".
Sample Input
6 6 .....# ##...# ##...# ..#..# .....# ###### 6 8 .....#.# ##.....# ##.....# .......# #......# #..#...# 0 0
Sample Output
Bad placement. There are 5 ships.
Source
CTU Open 2002
代码为:
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; const int maxn=1000+10; char map[maxn][maxn]; int min_x,min_y,max_x,max_y; int n,m,cal; int dx[]={-1,1,0,0,-1,-1,1,1}; int dy[]={0,0,-1,1,-1,1,-1,1}; void read_Graph() { char str[maxn]; for(int i=1;i<=n;i++) { scanf("%s",str+1); for(int j=1;j<=m;j++) map[i][j]=str[j]; } } bool check(int x,int y) { if(x>=1&&x<=n&&y>=1&&y<=m) return true; return false; } int dfs(int x,int y) { min_x=min(min_x,x); max_x=max(max_x,x); min_y=min(min_y,y); max_y=max(max_y,y); map[x][y]='.'; for(int i=0;i<8;i++) { int tx=x+dx[i]; int ty=y+dy[i]; if(map[tx][ty]=='#'&&check(tx,ty)) { cal++; dfs(tx,ty); } } return cal; } void solve() { int ans=0,area,i,j; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(map[i][j]=='#') { min_x=max_x=i; min_y=max_y=j; cal=1; area=dfs(i,j); if(area==(max_x-min_x+1)*(max_y-min_y+1)) ans++; else { ans=-1; break; } } if(ans==-1) break; } } if(ans==-1) printf("Bad placement.\n"); else printf("There are %d ships.\n",ans); } int main() { while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) return 0; read_Graph(); solve(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。