9届蓝桥杯：全球变暖

// 9届蓝桥全球变暖.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//思想：
/*

	
	

		遍历整个地图，找到一个未被标记过的，值为 # 的坐标。
	

	

		从这个坐标开始，从上下左右四个方向，标记相邻的 # 。
	

	

		把这些相邻的坐标，都标记下来，递归的进行标记，以便把相邻的相邻块也能标记上。
	

	

		待标记全部完成之后，将岛屿的计数 +1。
	

	

		回到第 1 步。如果第 1 步无法找到未标记的坐标，则结束。
	


*/

#include <iostream>
using namespace std;
char island[100][100];
int sum1=0,sum2=0, N;
void judge(int i,int j)//进行深度遍历DFS
{
    if (island[i][j] == '#')
    {
        island[i][j] = '1';
        if (j != 0)//对上进行标记
            judge(i, j - 1);
        if (j != N - 1)//对下进行标记
            judge(i, j + 1);
        if (i != 0)//对左进行标记
            judge(i - 1, j);
        if (i != N - 1)
            judge(i + 1, j);
    }
}
int main()
{
   int m, i, j, k;
   char n;
    cin >> N;
   
    for(i=0;i<N;i++)//输入
      for (j = 0; j < N; j++)
        {
            cin >> n;
            island[i][j] = n;
        }
    for(i=0;i<N;i++)//对岛屿进行清点标记
        for (j = 0; j < N; j++)
        {
            if (island[i][j] == '#')//以此为中心进行上下左右的标记
            {

                judge(i, j);
                sum1++;
            }
        }
    for (i = 0; i < N; i++)//海平面上升，对淹没的陆地标记为0
        for (j = 0; j < N; j++)
        {
            if (island[i][j] == '1')
            {
                if (j != 0 && island[i][j - 1] == '.')
                    island[i][j] = '0';
                else if (j != N - 1 && island[i][j + 1] == '.')
                    island[i][j] = '0';
                else if (i != 0 && island[i - 1][j] == '.')
                    island[i][j] = '0';
                else if (i != N - 1 && island[i + 1][j] == '.')
                    island[i][j] = '0';
            }
        }
    for (i = 0; i < N; i++)//将之前表为1的岛屿标为#
    {
        for (j = 0; j < N; j++)
        {
            if (island[i][j] == '1')
                island[i][j] = '#';
        }
       
    }
   /* for (i = 0; i < N; i++)//打印
    {
        for (j = 0; j < N; j++)
        {
            
               cout<< island[i][j];
        }
        cout << endl;
    }
    */
    for (i = 0; i < N; i++)//对淹没后的岛屿进行数量清点
        for (j = 0; j < N; j++)
        {
            if (island[i][j] == '#')//以此为中心进行上下左右的标记
            {

                judge(i, j);
                sum2++;
            }
        }
   
    cout << sum1 - sum2;


}
/*
7
.......
.##....
.##....
....##.
..####.
...###.
.......

这个例子在海平面上升后会增加岛屿的数量，所以结果为负数
10
##......##
##.###..##
##.###..##
##.###..##
##......##
##########
..........
###.......
.######...
..########
*/