全球变暖 DFS解决 C++

解题思路:
    类似于Flood Fill思路，刚开始我的思路是两次DFS，每次求联通岛屿个数，在两次之间先判断那些点临近海洋'.'，将这些点也变成海洋。但没有

AC，原因是对于有些岛屿，在被部分淹没后可能形成多个小岛，第二次DFS时会将它们看成多个岛屿从而出错。

    一种解决思路:一次DFS解决，在计算每个岛屿时分别记录岛屿陆地的个数及与海洋邻接岛屿的数目，若相等则该岛屿会被淹没，否则不会。

错误代码:

#include<cstdio>
#include<queue>
#include<cstring>
#include<utility>
using namespace std;

const int Max_N = 1010;
const int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};

int N;
char pic[Max_N][Max_N];
bool visited[Max_N][Max_N];

bool C(int x,int y)
{
	for(int i=0; i<4; i++ )
	{
		int nx = x + dx[i], ny = y + dy[i];
		if( 0<=nx&&nx<N && 0<=ny&&ny<N && pic[nx][ny]=='.' )
			return true;
	}
	return false;
}

void dfs(int x,int y)
{
	for( int i=0; i<4; i++ )
	{
		int nx = x + dx[i], ny = y + dy[i];
		if( 0<=nx&&nx<N && 0<=ny&&ny<N && !visited[nx][ny] && pic[nx][ny]=='#' )
		{
			visited[nx][ny] = true;
			dfs(nx,ny);
		}
	}
}

int main()
{
	int s = 0, e = 0;
	scanf("%d",&N);
	for( int i=0; i<N; i++ )
	{
		getchar();
		scanf("%s",pic[i]);
	}
	
	memset(visited,false,sizeof(visited));
	for( int i=0; i<N; i++ )
	{
		for( int j=0; j<N; j++ )
		{
			if( pic[i][j]=='#' && !visited[i][j] )
			{
				visited[i][j] = true;
				dfs(i,j);
				s++;	
			}	
		}	
	} 
	
	memset(visited,false,sizeof(visited));
	for( int i=0; i<N; i++ )
	{
		for( int j=0; j<N; j++ )
		{
			if( pic[i][j]=='#'  )
			{
				visited[i][j] = C(i,j);	
			}	
		}	
	} 
	for( int i=0; i<N; i++ )
	{
		for( int j=0; j<N; j++ )
		{
			if( visited[i][j]==true )	pic[i][j] = '.';	
		}	
	}
	
	printf("\n---------------------------------------------------------\n");
	for( int i=0; i<N; i++ )
	{
		puts(pic[i]);	
	} 
	
	memset(visited,false,sizeof(visited));
	for( int i=0; i<N; i++ )
	{
		for( int j=0; j<N; j++ )
		{
			if( pic[i][j]=='#' && !visited[i][j] )
			{
				visited[i][j] = true;
				dfs(i,j);
				e++;	
			}	
		}	 
	} 	
	
	printf("s=%d, e = %d\n",s,e);
	printf("%d\n",s-e);
	
	return 0;
}

参考代码:

/*
 *	全球变暖 : 直接两次dfs出错:因为在淹没后可能一个岛屿分裂成两个
 *二计数时会认为剩余两个
 *	解决方案1:直接在第一次dfs时就做出判断 
 */
#include<cstdio>

const int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
const int Max_N = 1e3+10;

int N;
int cnt, brink; //分别记录岛屿陆地个数、与海洋邻接岛屿的个数 
char pic[Max_N][Max_N];
bool visited[Max_N][Max_N]; //是否访问过该点 

void dfs(int x, int y);
bool C(int x, int y); //判断某点是否与海洋邻接 

int main()
{
	scanf("%d",&N);
	for( int i=0; i<N; i++ )
	{
		getchar();
		scanf("%s",pic[i]);
	}
	
	int ans = 0; //结果 
	for( int i=0; i<N; i++ )
	{
		for( int j=0; j<N; j++ )
		{
			if( !visited[i][j] && pic[i][j]=='#' )
			{
				cnt = brink = 0; //计数前初始化 
				visited[i][j] = true;
				dfs(i,j);
				if( cnt==brink )	ans++;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

bool C(int x,int y)
{
	for(int i=0; i<4; i++ )
	{
		int nx = x + dx[i], ny = y + dy[i];
		if( 0<=nx&&nx<N && 0<=ny&&ny<N && pic[nx][ny]=='.' )
			return true;
	}
	return false;
}

void dfs(int x, int y)
{
	cnt++;
	if( C(x,y) )	brink++;
	for( int i=0; i<4; i++ )
	{
		int nx = x + dx[i], ny = y + dy[i];
		if( 0<=nx&&nx<N && 0<=ny&&ny<N && !visited[nx][ny] && pic[nx][ny]=='#' )
		{
			visited[nx][ny] = true;
			dfs(nx,ny);
		}
	}
}