DFS和BFS定义

DFS

关于DFS，他叫做深度优先搜索，简称DFS，就是一条道走到黑，只要这里能够搜索，那么就不停地往下搜，往下搜，一直搜到不能搜为止，然后不能搜了直接返回上一层，然后继续搜，一直搜到不能搜为止。但是书上一直说DFS如果地图类型数据量很大的话会系统堆栈溢出……

BFS

关于BFS，他叫做广度优先搜索，简称BFS，就是一走走一圈，走完一圈走下一圈，是一层一层的走，如果DFS是一个知识点刨根问底型学习的话，BFS就是分区规划型学习，两种算法在不同的题目虽然都可以用到，但是效率却相差甚远,所以要去学习怎么搞算法……

题目

题目描述：

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数

输入：

整数0<=m,n<=100(m行，n列)

M行n列0到9的数字（中间没有空格）

输出：

细胞的个数

题解：

这道题就需要搜索了，首先枚举点，找到一个细胞的一部分就开始染色，用BFS或者DFS染成0，这样就不会干扰到寻找其他细胞了！然后一旦找到细胞的一部分就把这个细胞染成0色，这样找到一个一部分就找到了一个细胞，ans++就好了！

DFS染色：就是找到一个部分就向四周扩散，发现一个方向是细胞本身，扩散找到的细胞本身……

DFS代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int x1=x+dx[i];
        int y1=y+dy[i];
        if(a[x1][y1]!='0')
        {
            a[x1][y1]='0';
            dfs(x1,y1);
        }
    }
}

BFS代码：

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
void bfs(int x,int y)
{
    memset(q,0,sizeof(q));
    a[x][y]=0;
    int head,tail=1;
    q[tail][1]=x;
    q[tail][2]=y;
    for(head=1;head<=tail;head++)
    {
        int xx,yy;
        xx=q[head][1];
        yy=q[head][2];
        for(int i=0;i<4;i++)
        {
            int tx,ty;
            tx=xx+dx[i];
            ty=yy+dy[i];
            if(a[tx][ty]!='0')
            {
                q[++tail][1]=tx;
                q[tail][2]=ty;
                a[tx][ty]='0';
            }
        }
    }
}