洛谷Luogu-1331 海战（DFS） HQG_AC的博客

简单地DFS

1.读入，将字符串转化成数组

2.判断有没有两艘船接触

3.如果没有，dfs求出有几艘船

4.输出

详见代码：

#include
using namespace std;
int r,c,sum=0,d[5][3]; 
int f[1100][1100],flag=1;
void init()
{d[1][1]=0;d[1][2]=1;d[2][1]=1;d[2][2]=0;d[3][1]=0;d[3][2]=-1;d[4][1]=-1;d[4][2]=0;
} 
void dfs(int x,int y)
{for(int i=1;i<=4;i++)if(f[x+d[i][1]][y+d[i][2]]){f[x+d[i][1]][y+d[i][2]]=0; dfs(x+d[i][1],y+d[i][2]);}
}
int main()
{char x;memset(f,0,sizeof(f));cin>>r>>c;init() ;for(int i=1;i<=r;i++)for(int j=1;j<=c;j++){cin>>x;if(x=='.')f[i][j]=0;else f[i][j]=1;}for(int i=1;i<=r-1;i++) //判断有没有Bad placement.for(int j=1;j<=c-1;j++){int val=0;if(f[i][j]) val++;if(f[i+1][j]) val++;if(f[i][j+1]) val++;if(f[i+1][j+1]) val++;if(val==3) flag=0;//不能组成正方形 }for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)if(f[i][j]){		dfs(i,j); sum++;}if(flag)cout<<"There are "<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！