[数据结构与算法]试题 历届真题 全球变暖【第九届】【省赛】【B组】（DFS/BFS）

??

?该题是我之前在未学习搜索算法之前遇到的一道题，也正是这道题促使我去学习了搜索算法，如今回来AC它了~~~

? ? ? ? 1.DFS

该题实际上是一道标准模板题（看过我之前的文章的同学应该知道）

思路上：我们就遍历整个照片，如果遇到# ,我们即遇到岛屿了，那么我们就搜索这个岛屿（用book数组记录走过的地方）并给岛屿标号，同时我们查看这个岛屿上有没有四个方向都是陆地的，如果有那么我们就把以该岛屿号码为下标的数组++（即记录每个岛屿上四个方向都是陆地的地方的数量），最后我们遍历该数组，如果出现有岛屿没有有四个方向都是陆地的地方的话，那么ans++，最后输出ans即可

下面看代码

#include<iostream>
using namespace std;

char MAP[1005][1005];
int tx,ty,before=0,nextt[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int book[1005][1005]={0};
int ans[1000]={0};
void dfs(char MAP[][1005],int book[][1005],int x,int y,int n,int before)
{
	if(MAP[x][y+1]=='#'&&MAP[x+1][y]=='#'&&MAP[x][y-1]=='#'&&MAP[x-1][y]=='#')
	{
		ans[before]++;
	}
	if(MAP[x][y]=='#')
	{
		book[x][y]=1;
		for(int i=0;i<4;i++)
		{
			tx=x+nextt[i][0];
			ty=y+nextt[i][1];
			if(book[tx][ty]==1||tx<0||ty<0||tx>=n||ty>=n)
			continue;
			dfs(MAP,book,tx,ty,n,before);
		}
	}

	return ;
}

int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>MAP[i][j];
		}
	}
	//计算原来有多少岛屿
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(MAP[i][j]=='#'&&book[i][j]==0)
			{
				dfs(MAP,book,i,j,n,before);
				before++;				
			}
		}
	 } 
	 
	int sum=0;
	for(int i=0;i<before;i++)
	{
		if(ans[i]==0)
		{
			sum++;
		}
	 } 
	 cout<<sum<<endl;	 

	return 0;
 } 

? ? ? ? ?2.BFS

直接将我们上面的思路套入模板即可！！！

下面看代码

#include<iostream>
#include<queue>
using namespace std;

int book[1005][1005] = { 0 };
char MAP[1005][1005];
int before = 0, tx, ty, nextt[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int ans[1000] = { 0 };

void bfs(char MAP[][1005], int book[][1005], int x, int y, int n, int before)
{
	queue<pair<int, int> >q;
	q.push({ x,y });
	book[x][y] = 1;//初始化
	while (!q.empty())
	{
		pair<int, int>ij = q.front();
		if (MAP[ij.first][ij.second + 1] == '#' && MAP[ij.first + 1][ij.second] == '#' && MAP[ij.first][ij.second - 1] == '#' && MAP[ij.first - 1][ij.second] == '#')
		{
			ans[before]++;//寻找
		}
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			tx = ij.first + nextt[i][0];//注意这里是ij里面的数了，不是x和y了
			ty = ij.second + nextt[i][1];
			if (tx < 0 || ty < 0 || tx >= n || ty >= n || book[tx][ty] == 1 || MAP[tx][ty] == '.')
			{
				continue;
			}
			book[tx][ty] = 1;//判断走过！！！
			q.push({ tx,ty });
		}

	}
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> MAP[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (MAP[i][j] == '#'&&!book[i][j])//注意这里要判断有没有走过
			{
				bfs(MAP, book, i, j, n, before);
				before++;
			}
		}
	}
	int sum = 0;
	for (int i = 0; i < before; i++)
	{
		if (ans[i] == 0)
		{
			sum++;
		}
	}
	cout << sum << endl;
	return 0;
}

如果有小伙伴在看过题解之后还无法理解的话，可以自行调试跟着走一遍代码