本文主要是介绍P1331 海战，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目传送门：P1331 海战
dfs求联通块
如果遇到船只就把船只数加一，然后搜索把这个船只全部标位海，防止以后的重复搜索。
代码：
#include<bits/stdc++.h>
using namespace std;
char g[1005][1005];
int n,m;
bool check(int x,int y){int cnt=0;if(g[x][y]=='#') cnt++;if(g[x+1][y]=='#') cnt++;if(g[x][y+1]=='#') cnt++;if(g[x+1][y+1]=='#') cnt++;return cnt==3;
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ cin>>g[i][j];}}for(int i=1;i<n;i++){for(int j=1;j<m;j++){if(check(i,j)){printf("Bad placement.\n");return 0;}}}int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(g[i][j]=='#' && g[i-1][j]!='#' && g[i][j-1]!='#')ans++;}}printf("There are %d ships.\n",ans);return 0;
}这篇关于P1331 海战的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
