蓝桥杯2018 B组 第九题

#include <bits/stdc++.h>

#define M 1005

using namespace std;

int n;

char map1[M][M];

bool vis[M][M];

int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

void dfs(int x,int y)

{

	vis[x][y] = 1;

	for(int i = 0; i < 4; i++)

	{

		int dx = x + dir[i][0];

		int dy = y + dir[i][1];

		if(dx >= 0 && dy >=0 && dx < n && dy < n && !vis[dx][dy] && map1[dx][dy] == '#')

			dfs(dx,dy);

	}

}

int main()

{

	cin>>n;

	int begin_count = 0,end_count = 0;

	for(int i = 0; i < n; i++)

		for(int j = 0; j < n; j++)

			cin>>map1[i][j];

	/*统计开始前岛屿个数*/

	for(int i = 0; i < n; i++)

		for(int j = 0; j < n; j++)

		{

			if(map1[i][j] == '#' && !vis[i][j])

				begin_count++,dfs(i,j);

		}

	/*淹没过程*/

	memset(vis,0,sizeof(vis));

	for(int i = 1; i < n-1; i++)

		for(int j = 1; j < n-1; j++)

		{

			if(map1[i][j] == '#'){

				if((map1[i+1][j]=='.'||map1[i-1][j]=='.'||map1[i][j+1]=='.'||map1[i][j-1]=='.'))

				map1[i][j] = '1';

			}

		}

	/*统计结束后岛屿个数*/

	memset(vis,0,sizeof(vis));

	for(int i = 0; i < n; i++)

		for(int j = 0; j < n; j++)

		{

			if(map1[i][j] == '#' && !vis[i][j])

				end_count++,dfs(i,j);

		}

	cout<<begin_count - end_count<<"\n";

	return 0;

}

比较简单的搜索题目，