9_19，洛谷刷题记录

要做一株小草，默默努力

求细胞数量

#include
using namespace std;
//对每个点进行搜索，dfs/bfs，将搜过的点标记出来，然后记录次数
//搜索几次，就有几个细胞
const int N=110;
int g[N][N],st[N][N];
int n,m;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

void dfs(int x,int y)
{
    if(g[x][y]==0) return;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(st[a][b]==0&&g[a][b]) 
        {
            st[a][b]=1;
            dfs(a,b);
            //st[a][b]=0;
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            scanf("%1d",&g[i][j]);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if(g[i][j]&&st[i][j]==0) 
            {
                dfs(i,j);
                cnt++;
            }
    }
    printf("%d",cnt);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

1.我们不能在dfs进行递归的时候回复现场，回复现场在回溯的时候进行的，但是我们的算法的思想是每次递归下去，将与他相接的不为0的空间标记为1，所以根本不需要进行回溯
2.第二个槽点就是在数据读入的时候，
4 10
0234500067
1034560500
2045600671
0000000089
这些数据是连在一起的，如果直接读入的话，会认为全部是一个数字，也就是说0234500067会放到第一个空间中存起来，就造成了错误，所以我们需要进行重新的数据读入
方法一：scanf(“%1d”,&x);
方法二：一字符串类型读入，将读入的数据按位转化为数字存起来