蓝桥杯2018年第九届真题-全球变暖-题解(C++代码)

1304 阅读 3 评论 0 点赞

原题链接：蓝桥杯2018年第九届真题-全球变暖

dfs
    #include<iostream>
    using namespace std;
    int N;
    char a[1005][1005];
    int book[1005][1005];
    int four[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    bool judge(int x,int y)//判断这个点会不会被淹没
    {
    	if(a[x-1][y]=='#'&&a[x+1][y]=='#'&&a[x][y-1]=='#'&&a[x][y+1]=='#')
    	  return true;
    	else return false;
    }
    bool flag=0;
    void dfs(int x,int y)
    {
    	for(int k=0;k<4;k++)
    	{
    		int tx=x+four[k][0];
    		int ty=y+four[k][1];
    		if(tx<1||tx>N||ty<1||ty>N)continue;
    		if(a[tx][ty]=='#'&&book[tx][ty]==0)
    		{
    			book[tx][ty]=1;
    			if(judge(tx,ty))flag=1;
    			dfs(tx,ty);
    		}
    	}
    }
    int main()
    {
    	ios::sync_with_stdio(false);
    	cin>>N;
    	for(int i=1;i<=N;i++)
    	  for(int j=1;j<=N;j++)
    	    cin>>a[i][j];
    	int cnt1=0,cnt2=0;//cnt1:初始岛屿数 cnt2:全球变暖后岛屿数
    	for(int i=1;i<=N;i++)
    	{
    		for(int j=1;j<=N;j++)
    		{
    			if(a[i][j]=='#'&&book[i][j]==0)
    			{
    				book[i][j]=1;
    				flag=0;
    				dfs(i,j);
    				cnt1++;
    				if(flag)cnt2++;	
    			}	
    		}
    	}
    	cout<<cnt1-cnt2;
    	return 0;
    } 
        
    
bfs
    #include<iostream>
    #include<queue>
    using namespace std;
    int N;
    char a[1005][1005];
    int book[1005][1005];
    int four[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    struct node
    {
    	int x,y;
    };
    bool judge(int x,int y)
    {
    	if(a[x-1][y]=='#'&&a[x+1][y]=='#'&&a[x][y-1]=='#'&&a[x][y+1]=='#')
    	  return true;
    	else return false;
    }
    bool flag=0;
    void bfs(int x,int y)
    {
    	queue<node> q;
    	node temp;
    	temp.x=x,temp.y=y;
    	q.push(temp);
    	while(!q.empty())
    	{
    		temp=q.front();
    		q.pop();
    		for(int k=0;k<4;k++)
    		{
    			int tx=temp.x+four[k][0];
    			int ty=temp.y+four[k][1];
    			if(tx<1||tx>N||ty<1||ty>N)continue;
    			if(a[tx][ty]=='#'&&book[tx][ty]==0)
    			{
    				book[tx][ty]=1;
    				if(judge(tx,ty))flag=1;
    				temp.x=tx,temp.y=ty;
    				q.push(temp);
    			}
    		}
    	}
    	
    }
    int main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	cin>>N;
    	for(int i=1;i<=N;i++)
    	  for(int j=1;j<=N;j++)
    	    cin>>a[i][j];
    	int cnt1=0,cnt2=0;
    	for(int i=1;i<=N;i++)
    	{
    		for(int j=1;j<=N;j++)
    		{
    			if(a[i][j]=='#'&&book[i][j]==0)
    			{
    				book[i][j]=1;
    				flag=0;
    				bfs(i,j);
    				cnt1++;
    				if(flag)cnt2++;	
    			}	
    		}
    	}
    	cout<<cnt1-cnt2;
    	return 0;
    }

0.0分

6 人评分

本文分类：题解列表
浏览次数：1304 次浏览
发布日期：2020-04-09 13:32:30
本文链接：https://blog.dotcpp.com/a/69200

上一篇 > [编程入门]自定义函数之字符类型统计-题解(Java代码)
下一篇 > [编程入门]利润计算-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯2018年第九届真题-全球变暖-题解(C++代码)

评论列表共有 3 条评论

发表评论取消回复

训练

蓝桥杯2018年第九届真题-全球变暖-题解(C++代码)

1286: 最大配对

Py2854-密码翻译-简洁

一步步慢慢来，不要急，不要慌

题解 2777: 计算2的幂

评论列表 共有 3 条评论

发表评论 取消回复

评论列表共有 3 条评论

发表评论取消回复