DFS之~

#include <bits/stdc++.h>
using namespace std;
int a[1010][1010];
int n,m;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int cnt,maxl;
bool pre_check(int a,int b,int c,int d) {
	int ans=0;
	if(a==1) {
		ans++;
	}
	if(b==1) {
		ans++;
	}
	if(c==1) {
		ans++;
	}
	if(d==1) {
		ans++;
	}
	if(ans==3) {
		return false;
	}
	return true;
}
void dfs(int x,int y) {
	a[x][y]=0;
	int sx,sy;
	for(int i=0;i<4;i++) {
		sx=x+dx[i];
		sy=y+dy[i];
		if(a[sx][sy]==1) {
			dfs(sx,sy);
		}
	}
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			char ch;
			cin>>ch;
			if(ch=='#') {
				a[i][j]=1;
			}
			if(ch=='.') {
				a[i][j]=0;
			}
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			if(!pre_check(a[i][j],a[i][j+1],a[i+1][j],a[i+1][j+1])) {
				//int sum=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
				cout<<"Bad placement."<<endl;
				exit(0);
			}
		}
	}
	//cout<<"Pre-check passed"<<endl;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(a[i][j]==1) {
				dfs(i,j);
				cnt++;
				maxl=max(maxl,cnt);
			}
		}
	}
	cout<<"There are "<<cnt<<" ships."<<endl;
	return 0;
}

这道题呢看上去是有点难度的，但只要仔细思考，我们就不难发现——

• 如果答案是Bad placement.，所贴在一起的船必定有一个地方是3个“#”

所以我们的思路大致如下：

• 首先遍历数组，发现有3个“#”立即输出Bad placement.，结束程序。
• 否则使用广搜，计算出连通块的个数，最后输出答案。

代码如下：

#include<iostream>
#include<queue>
using namespace std;
int n,m,ans,a[1005][1005];
int xx[4]={-1,0,1,0},yy[4]={0,1,0,-1};
char ch;
struct id
{
	int x,y;
};
void bfs(int x,int y)
{
	queue<id>q;
	q.push(id{x,y});
	a[x][y]=0;
	while(!q.empty())
	{
		int tx=q.front().x;
		int ty=q.front().y;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=tx+xx[i];
			int ny=ty+yy[i];
			if(a[nx][ny]==1)
			{
				q.push(id{nx,ny});
				a[nx][ny]=0;
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>ch;
			if(ch=='.')a[i][j]=0;
			else a[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int sum=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
			if(sum==3)
			{
				cout<<"Bad placement.";
				return 0;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==1)
			{
				bfs(i,j);
				ans++;
			}
		}
	}
	cout<<"There are "<<ans<<" ships.";
	return 0;
}

记得好评，球球了！

Dfs

#include<bits/stdc++.h>
using namespace std;
bool a[1001][1001]={0};
void dfs(int x,int y)
{
	a[x][y]=0;
	if(a[x+1][y]) dfs(x+1,y);
	if(a[x-1][y]) dfs(x-1,y);
	if(a[x][y+1]) dfs(x,y+1);
	if(a[x][y-1]) dfs(x,y-1);
	return;
}
bool d(int i,int j)
{
	int c=0;
	if(a[i][j])c++;
	if(a[i+1][j])c++;
	if(a[i][j+1])c++;
	if(a[i+1][j+1])c++;
	if(c==3)return 0;
	return 1;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char b;
			cin>>b;
			if(b=='.') a[i][j]=0;
			else if(b=='#') a[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i<n and j<m and !d(i,j))
			{
				cout<<"Bad placement.";
				return 0;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j])
			{
				ans++;
				dfs(i,j);
			}
		}
	}
	cout<<"There are "<<ans<<" ships.";
	return 0;
}