7 条题解

  • 2
    @ 2025-3-9 14:14:57

    简单的连通块

    变量

    题目要求：定义长宽N,MN,M，输入一个地图，长宽都≤100\le100，则maps[105][105]maps[105][105]即可。 此外，还需要vis[105][105]vis[105][105]记录是否访问过，fx[4]={1,0,−1,0},fy[4]={0,1,0,−1}fx[4]=\{1,0,-1,0 \},fy[4]=\{0,1,0,-1 \}求x,yx,y方向增减，ss记录山的总数。

    int n,m;//地图长宽
bool maps[105][105],vis[105][105];//造地图
char ch;//不想用字符
int s=0;//山的总数
int fx[4]={1,0,-1,0};//x坐标
int fy[4]={0,-1,0,1};//y坐标

    主函数

    负责输入，及寻找山和记录山的总数。

    int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>ch;
            if(ch=='#')maps[i][j]=1;//字符转布尔
            else if(ch=='-')maps[i][j]=0;//造山
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maps[i][j]==1&&vis[i][j]==0){//找山
                dfs(i,j);
                s++;//找到就+1
            }
        }
    }
    cout<<s;//输出山的数量
}

    DFS

    四处寻找附近的山，再走过去继续找。

    void dfs(int x,int y){
    vis[x][y]=1;//走过了
    for(int i=0;i<4;i++){//找附近的山
        int xx=x+fx[i];
        int yy=y+fy[i];
        if(xx>=0&&xx<=n&&yy>=0&&y<=m&&maps[xx][yy]==1&&vis[xx][yy]!=1){//在不在范围，是不是山，走没走过
            dfs(xx,yy);
        }
    }
}

    AC code

    #include<bits/stdc++.h>
using namespace std;
int n,m;//地图长宽
bool maps[105][105],vis[105][105];//造地图
char ch;
int s=0;//山的总数
int fx[4]={1,0,-1,0};//x坐标
int fy[4]={0,-1,0,1};//y坐标
void dfs(int x,int y){
    vis[x][y]=1;//走过了
    for(int i=0;i<4;i++){//找附近的山
        int xx=x+fx[i];
        int yy=y+fy[i];
        if(xx>=0&&xx<=n&&yy>=0&&y<=m&&maps[xx][yy]==1&&vis[xx][yy]!=1){//在不在范围，是不是山，走没走过
            dfs(xx,yy);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>ch;
            if(ch=='#')maps[i][j]=1;
            else if(ch=='-')maps[i][j]=0;//造山
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maps[i][j]==1&&vis[i][j]==0){//找山
                dfs(i,j);
                s++;//找到就+1
            }
        }
    }
    cout<<s;//输出山的数量
}
    • 1
      @ 2025-3-15 20:59:39

      《群山总数》题解

      这是一题是一个非常简单的DFS求连通块题目 （简单的我都要吐了）

      第一步 看题目 题目详情

      首先 定义一个105^2^的数组，两个没啥用的dx、dy数组，还有三个变量n、m和sum。

      int dx[4] = { 0,0,1,-1 }；
int dy[4] = { 1,-1,0,0 };//两个方向数组
char c[110][110];//保持地图
int n, m, sum;//地图的长、宽，连通块的数量

      接下来 先写好用的main函数以及输入

      int main() {
  cin >> n >> m;
  for (int i = 1;i <= n;i++)
    for (int j = 1;j <= m;j++)
      cin >> c[i][j];
}//输入

      紧接着 写普通的循环+🔎连通块+输出

        for (int i = 1;i <= n;i++)
    for (int j = 1;j <= m;j++)
  		if (c[i][j] == '#') { 
        sum++;//累加器求和
        c[i][j] = '-';//标记
        dfs(i, j);//函数搜索标记
  }cout << sum << endl;
  return 0;//随手好习惯

      然后 是核心代码————DFS函数

      void dfs(int x, int y) {
	for (int i = 0;i < 4;i++) {
  int nx = x + dx[i], ny = y + dy[i];
		if (nx > 0 && nx <= n && ny > 0 && ny <= m && c[nx][ny] == '#') {
			c[nx][ny] = '-';
      dfs(nx, ny);
		}
	}
}

      最后 晒出整个代码

      #include <iostream>
using namespace std;
int dx[4] = { 0,0,1,-1 }；
int dy[4] = { 1,-1,0,0 };
char c[110][110];
int n, m, sum;
void dfs(int x, int y) {
	for (int i = 0;i < 4;i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx > 0 && nx <= n && ny > 0 && ny <= m && c[nx][ny] == '#') {
			c[nx][ny] = '-';
			dfs(nx, ny);
		}
	}
}int main() {
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
		cin >> c[i][j];
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
		if (c[i][j] == '#') { 
		sum++;
		c[i][j] = '-';
		dfs(i, j);
	 }cout << sum << endl;
	return 0;
}

      谢谢大家 （麻烦给个👍呗，求求了） 。

      • 1
        @ 2025-3-9 12:50:07

        先阅读题目：题目出现两个变量N,M,还有一个char类型的沙盘a,另外还有一个答案（山的数量）ans。 因为是深搜题，还需要三个变量:vis,dx,dx,vis由于记录点是否被访问，dx和dy用于深搜时x,y方向的增减。

        int n,m,ans;
char a[105][105];
bool vis[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

        接下来编主函数 首先要按题目要求输入n,m,a

        cin>>n>>m;
for(int i=0;i<n;i++){	
    for(int j=0;j<m;j++){
        cin>>a[i][j];
    }
}

        (至于为啥不把dfs放输入里，自己试试看就知道了) 接下来遍历一遍a,找出一座山(一定要是没被访问过的山)并把它标记为被访问过就可以进深搜函数了(这里先不讲深搜)把一座山深搜完，应增加ans，表示发现了一座山。

        for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(a[i][j]=='#'&&vis[i][j]==false){
            vis[i][j]=true;
            dfs(i,j);
            ans++;
        }
    }
}

        好了，现在还有输出，题目要求输出山的数量就是输出ans

        cout<<ans;

        这样子主函数就差不多了 主函数:

        int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){	
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j]=='#'&&vis[i][j]==false){
				vis[i][j]=true;
				dfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

        接下来是深搜(我喜欢用void,这个根据个人喜好决定，不同的当然要作相应修改)，定义x,y作当前节点的坐标 首先，因为没有终点，所以不写if和return,深搜完就直接退出，先写一个for,用来搜索四面的节点，这里要临时定义xx=dx[i]+x,yy=dy[i]+y，用来保存四面节点，然后判断节点是否满足以下四个条件: 1.不出界； 2.没有被标记； 3.是山； 满足了就可以从xx,yy继续深搜(注意vis)。 这样dfs就编完了,注意要把它放在主函数前。

        void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=0&&yy>=0&&xx<n&&yy<m&&vis[xx][yy]==false&&a[xx][yy]=='#'){
			vis[xx][yy]=true;
			dfs(xx,yy);
		}
	}
}

        样例代码：

        #include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char a[105][105];
bool vis[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=0&&yy>=0&&xx<n&&yy<m&&vis[xx][yy]==false&&a[xx][yy]=='#'){
			vis[xx][yy]=true;
			dfs(xx,yy);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){	
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j]=='#'&&vis[i][j]==false){
				vis[i][j]=true;
				dfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

        第一次写题解QwQ求大佬给意见，求支持QwQ

        • 0
          @ 2025-4-21 19:20:50 
           一个蒟蒻 (戴嘉磊) LV 4 @ 1 个月前 
《群山总数》题解
这是一题是一个非常简单的DFS求连通块题目 （简单的我都要吐了）

第一步 看题目 题目详情

首先 定义一个105^2^的数组，两个没啥用的dx、dy数组，还有三个变量n、m和sum。

int dx[4] = { 0,0,1,-1 }；
int dy[4] = { 1,-1,0,0 };//两个方向数组
char c[110][110];//保持地图
int n, m, sum;//地图的长、宽，连通块的数量
接下来 先写好用的main函数以及输入

int main() {
  cin >> n >> m;
  for (int i = 1;i <= n;i++)
    for (int j = 1;j <= m;j++)
      cin >> c[i][j];
}//输入
紧接着 写普通的循环+🔎连通块+输出

  for (int i = 1;i <= n;i++)
    for (int j = 1;j <= m;j++)
  		if (c[i][j] == '#') { 
        sum++;//累加器求和
        c[i][j] = '-';//标记
        dfs(i, j);//函数搜索标记
  }cout << sum << endl;
  return 0;//随手好习惯
然后 是核心代码————DFS函数

void dfs(int x, int y) {
	for (int i = 0;i < 4;i++) {
  int nx = x + dx[i], ny = y + dy[i];
		if (nx > 0 && nx <= n && ny > 0 && ny <= m && c[nx][ny] == '#') {
			c[nx][ny] = '-';
      dfs(nx, ny);
		}
	}
}
最后 晒出整个代码

#include <iostream>
using namespace std;
int dx[4] = { 0,0,1,-1 }；
int dy[4] = { 1,-1,0,0 };
char c[110][110];
int n, m, sum;
void dfs(int x, int y) {
	for (int i = 0;i < 4;i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx > 0 && nx <= n && ny > 0 && ny <= m && c[nx][ny] == '#') {
			c[nx][ny] = '-';
			dfs(nx, ny);
		}
	}
}int main() {
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
		cin >> c[i][j];
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
		if (c[i][j] == '#') { 
		sum++;
		c[i][j] = '-';
		dfs(i, j);
	 }cout << sum << endl;
	return 0;
}
谢谢大家 （麻烦给个👍呗，求求了） 。
          • 0
            @ 2025-4-21 19:19:51 
            using namespace std;
int n,m,ans;
char a[105][105];
bool vis[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=0&&yy>=0&&xx<n&&yy<m&&vis[xx][yy]==false&&a[xx][yy]=='#'){
			vis[xx][yy]=true;
			dfs(xx,yy);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){	
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j]=='#'&&vis[i][j]==false){
				vis[i][j]=true;
				dfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

            一个蒟蒻 (戴嘉磊) LV 4 @ 1 个月前 《群山总数》题解 这是一题是一个非常简单的DFS求连通块题目 （简单的我都要吐了）

            第一步 看题目 题目详情

            首先 定义一个105^2^的数组，两个没啥用的dx、dy数组，还有三个变量n、m和sum。

            int dx[4] = { 0,0,1,-1 }； int dy[4] = { 1,-1,0,0 };//两个方向数组 char c[110][110];//保持地图 int n, m, sum;//地图的长、宽，连通块的数量 接下来 先写好用的main函数以及输入

            int main() { cin >> n >> m; for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) cin >> c[i][j]; }//输入 紧接着 写普通的循环+🔎连通块+输出

            for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) if (c[i][j] == '#') { sum++;//累加器求和 c[i][j] = '-';//标记 dfs(i, j);//函数搜索标记 }cout << sum << endl; return 0;//随手好习惯 然后 是核心代码————DFS函数

            void dfs(int x, int y) { for (int i = 0;i < 4;i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx > 0 && nx <= n && ny > 0 && ny <= m && c[nx][ny] == '#') { c[nx][ny] = '-'; dfs(nx, ny); } } } 最后 晒出整个代码

            #include using namespace std; int dx[4] = { 0,0,1,-1 }； int dy[4] = { 1,-1,0,0 }; char c[110][110]; int n, m, sum; void dfs(int x, int y) { for (int i = 0;i < 4;i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx > 0 && nx <= n && ny > 0 && ny <= m && c[nx][ny] == '#') { c[nx][ny] = '-'; dfs(nx, ny); } } }int main() { cin >> n >> m; for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) cin >> c[i][j]; for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) if (c[i][j] == '#') { sum++; c[i][j] = '-'; dfs(i, j); }cout << sum << endl; return 0; } 谢谢大家 （麻烦给个👍呗，求求了） 。

            • 0
              @ 2025-3-15 22:18:35

              这也是一个连通块基础题好吧！

              1.首先，我们先来定义一下变量
              int n,m,ans;
char a[105][105];
bool vis[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
              2.接下来就是最最最简单的主函数部分了
              int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){	
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
              此处我想每个人都会吧（除！@#外）
              	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j]=='#'&&vis[i][j]==0){
				vis[i][j]=1;
				dfs(i,j);
				ans++;
			}
		}
	}
              最后的最后，被忘了输出
              cout<<ans;
return 0;
              3.接下来，最难的函数部分到了（但还是无敌的简单）
              void dfs(int x,int y){
for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=0&&yy>=0&&xx<n&&yy<m&&vis[xx][yy]==0&&a[xx][yy]=='#'){
			vis[xx][yy]=1;
			dfs(xx,yy);
		}
	}
}
              4.最后最后最后全部代码就在下方了（应该没人不会吧）
              #include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char a[105][105];
bool vis[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y){
for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=0&&yy>=0&&xx<n&&yy<m&&vis[xx][yy]==0&&a[xx][yy]=='#'){
			vis[xx][yy]=1;
			dfs(xx,yy);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){	
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j]=='#'&&vis[i][j]==0){
				vis[i][j]=1;
				dfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

              第一次发题解请大家互相关照（点亿个赞哦）！！！！！！！

              拜拜

              • 0
                @ 2025-3-15 22:00:05

                一，分析： 一张n*m的地图，有山（不一定联通）和水，求山数量。 二，思路： 1.常规： 访问地图，打上标记。 2，不常规： 进入'#'处（'-'处不访问），寻找与它相邻的'#'。所以只要找到没打过标记的'#'答案+1。 如下：

                	for(int i=0;i<n;i++){
		for(int j=0;j<k;j++){
			if(map[i][j]=='#'&&vis[i][j]==0){
				ans++;
				dfs(i,j);
			}
		}
	}

                按上述微微润色一下dfs函数就好了~~

                void dfs(int x,int y){ 
    if(x<0||x>=n||y<0||y>=k||vis[x] 
    [y]1||map[x][y]'-')
        return;
    vis[x][y]=1;
    dfs(x+1,y);
    dfs(x-1,y);
    dfs(x,y+1);
    dfs(x,y-1);
}

                故代码如下：

                #include<iostream>
using namespace std;
int n,k;
char map[110][110];
int vis[110][110];
int ans=0;
void dfs(int x,int y){
	if(x<0||x>=n||y<0||y>=k||vis[x][y]==1||map[x][y]=='-') return;
	vis[x][y]=1;
	dfs(x+1,y);
	dfs(x-1,y);
	dfs(x,y+1);
	dfs(x,y-1);
}
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<k;j++){
			cin>>map[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<k;j++){
			if(map[i][j]=='#'&&vis[i][j]==0){
				ans++;
				dfs(i,j);
			}
		}
	}
	cout<<ans;
	return 0;
}
                • 1

                群山总数

                信息

                ID
                2744
                时间
                1000ms
                内存
                256MiB
                难度
                5
                标签
                递交数
                57
                已通过
                23
                上传者
                1. 关于
                2. 联系我们
                3. 隐私
                4. 服务条款
                5. 版权申诉
                6. Language
                7. 兼容模式
                8. 主题
                3. Worker 0, 131ms
                4. Powered by Hydro v4.18.1 Community