18信二孙笑柯

用户名：1241383587

访问量：3000

签　名：

等　　级
排　　名	658
经　　验	3890
参赛次数	10
文章发表	5
年　　龄	19
在职情况	学生
学　　校	河南农业大学
专　　业	电子信息科学与技术

　　自我简介：

TA的其他文章

蓝桥杯2018年第九届真题-日志统计-题解(C++代码)
浏览：755

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

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

　　作者: 18信二孙笑柯　　　　发表时间：2020-04-09 13:32:30 浏览：805　|　评论：2　

原题链接：蓝桥杯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分

11 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

烟花烫头

一楼牛逼，看的真细

2020-09-20 15:43:46

二分之三

兄弟，你的bfs代码temp那个地方出了个问题你直接 temp.x=tx,temp.y=ty;    与前面的int tx=temp.x+four[k][0];
            int ty=temp.y+four[k][1];出现了冲突每次 temp.x和temp.y都发生了改变没有达到bfs的要求。
你看一下，欢迎回复。

2020-07-28 13:02:24

18信二孙笑柯

TA的其他文章

你可能喜欢

统计字符（C语言描述运用ctype.h）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-公约公倍（C语言代码）

简单的a+b （C语言代码）

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

评论区

精彩推荐

人见人爱A+B （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

【计算两点间的距离】（C语言代码）

蛇行矩阵（C语言代码）

1009题解

Cylinder （C语言描述+详细分析）

A+B for Input-Output Practice (VI) （C语言代码）

1035 题解

蛇行矩阵（C语言代码）

输入输出格式练习（C语言代码）

18信二孙笑柯

TA的其他文章

你可能喜欢

统计字符 （C语言描述运用ctype.h）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

简单的a+b （C语言代码）

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

评论区

精彩推荐

人见人爱A+B （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

【计算两点间的距离】 （C语言代码）

蛇行矩阵 （C语言代码）

1009题解

Cylinder （C语言描述+详细分析）

A+B for Input-Output Practice (VI) （C语言代码）

1035 题解

蛇行矩阵 （C语言代码）

输入输出格式练习 （C语言代码）

统计字符（C语言描述运用ctype.h）

C二级辅导-公约公倍（C语言代码）

　　评论区

【计算两点间的距离】（C语言代码）

蛇行矩阵（C语言代码）

蛇行矩阵（C语言代码）

输入输出格式练习（C语言代码）