洛谷-P1331海战-DFS与BFS解法

题目描述

在一个方形的盘上，放置了固定数量和形状的船只，每只船却不能碰到其它的船。在本题中，我们认为船是方形的，所有的船只都是由图形组成的方形。

求出该棋盘上放置的船只的总数。

输入格式

第一行为两个整数 R 和 C，用空格隔开，分别表示游戏棋盘的行数和列数。

接下来 R 行，每行 C个字符，为 # 或 .。# 表示船只的一部分，. 表示水。

输出格式

一行一个字符串，如果船的位置放得正确（即棋盘上只存在相互之间不能接触的方形，如果两个 # 号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相互接触了）。就输出 There are S ships.，S 表示船只的数量。否则输出 Bad placement.。

样例 #1

样例输入 #1

6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#

样例输出 #1

There are 5 ships.

提示

对于 100% 的数据，1<=R, C <=1000

一、BFS解法

#include <bits/stdc++.h>
using namespace std;
#define N 1002
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char Map[N][N]={0};
int done[N][N]={0};
int r,c,cnt=0;
typedef pair<int,int> PII;
queue<PII> q;
PII temppair;

int check(int x, int y)
{
  /*
	用以判断是否存在错误摆放的船只
	众所周知船是方形的，遇到直角的肯定就是错误摆放
	也就是下面这四种情况
	#.   ##   .#  ## 
	##   #.   ##  .#
	观察发现，符合直角的情况都是在四个格子内有三个'#'
	只需要使用一个2*2大小的框，判断这里面的'#'数量是否=3即可
	这也是这道题的难点 
	*/
	if(x<1 || x>r || y<1 || y>c)
		return 0;
	if(done[x][y]==1)
		return 0;
	if(Map[x][y]=='.')
		return 0;
	return 1;
	
}
void bfs(){
	while(!q.empty())
	{
		temppair = q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nowx = dx[i] + temppair.first;
			int nowy = dy[i] + temppair.second;
			if(check(nowx,nowy))
			{
				q.push({nowx,nowy});
				done[nowx][nowy]=1;
			}
		}
	}
}

int pd(int x,int y)  
{
	
	int cnt1=0;
	if(Map[x][y]=='#') cnt1++;
	if(Map[x][y+1]=='#') cnt1++;
	if(Map[x+1][y]=='#') cnt1++;
	if(Map[x+1][y+1]=='#') cnt1++;
	if(cnt1==3) return 1;
	return 0;
}

int main()
{
	bool flag = false;
	cin>>r>>c;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
			cin>>Map[i][j];
	
	for(int i=1;i<=r-1;i++)
	{
		if(!flag)
		{
			for(int j=1;j<=c-1;j++)
				if(pd(i,j))
				{
					flag = true;
					break;
				}
		}
		else
			break;
	}
	if(!flag)
		for(int i=1;i<=r;i++)
		{
			for(int j=1;j<=c;j++)
			{
				if(Map[i][j]=='#' && done[i][j]==0)
				{
					q.push({i,j});
					bfs();
					cnt++;
				}
			}	
		}
	if(!flag)
		printf("There are %d ships.",cnt);
	else
		cout<<"Bad placement.";
	return 0;
}

二、DFS解法

#include <bits/stdc++.h>
using namespace std;
#define N 1002
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char Map[N][N]={0};
int done[N][N]={0};
int r,c,cnt=0;

int check(int x, int y)
{
	if(done[x][y]==1)
		return 0;
	if(Map[x][y]=='.')
		return 0;
	return 1;
	
}
void dfs(int x,int y){
	if(x<1 || x>r || y<1 || y>c)
		return ;
	for(int i=0;i<4;i++)
	{
		int nowx = x+dx[i];
		int nowy = y+dy[i];
		if(check(nowx,nowy))
		{
			done[nowx][nowy]=1;  //本题的DFS也无需回溯
			dfs(nowx,nowy);
		}
	}
}

int pd(int x,int y)  
{
	int cnt1=0;
	if(Map[x][y]=='#') cnt1++;
	if(Map[x][y+1]=='#') cnt1++;
	if(Map[x+1][y]=='#') cnt1++;
	if(Map[x+1][y+1]=='#') cnt1++;
	if(cnt1==3) return 1;
	return 0;
}

int main()
{
	bool flag = false;
	cin>>r>>c;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
			cin>>Map[i][j];
	
	for(int i=1;i<=r-1;i++)
	{
		if(!flag)
		{
			for(int j=1;j<=c-1;j++)
				if(pd(i,j))
				{
					flag = true;
					break;
				}
		}
		else
			break;
	}
	if(!flag)
		for(int i=1;i<=r;i++)
		{
			for(int j=1;j<=c;j++)
			{
				if(Map[i][j]=='#' && done[i][j]==0)
				{
					dfs(i,j);
					cnt++;
				}
			}	
		}
	if(!flag)
		printf("There are %d ships.",cnt);
	else
		cout<<"Bad placement.";
	return 0;
}