题解 P1451 【求细胞数量】

秉烛顷夜 · 2019-07-26 18:42:56 · 题解

这题一看到应该就可以反应过来是搜连通块的题

搜法分为dfs和bfs

先看样例发现是一串数字所以无法写以下代码

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) 
        scanf("%d",&a[i][j]);

那该怎么办

//用字符呗
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        char c;
        cin>>c;
        a[i][j]=c-'0';
    } 

或者

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) 
        scanf("%1d",&a[i][j]);//%1d表示只读一位

输入完那就开始搜索吧

先讲bfs

bfs通常会用到队列

这里我推荐一个stl的双向队列，叫做deque

/*
队列基本操作： 
deque<int> q;创建一个数双端队列q,int也可以是别的类型
q.empty();判断队列是否为空，为空返回true
q.push_front(s);将s从队头入队
q.push_back(s);将s从队尾入队,和普通队列方式一样
q.front();只返回队头元素
q.back();只返回队尾元素
q.pop_front();将队头元素弹出
q.pop_back;将队尾元素弹出
q.clear();将队列清空
*/

bfs是一层一层搜的 框架如下

//bfs模板
struct ed
{
    .....
}
deque<ed>q;
void bfs()
{
    标记起点 
    起点入队列 
    while(!q.empty())//队列不为空 
    {
        ed nw=q.front();//返回队首
        for(拓展出接下来可能的状态)
        {
            ed nxt;
            记录这一状态
            判断状态是否合法 
            标记状态 
            q.push_back(nxt);//状态入队列 
        }
        q.pop_front();//弹出队首 
    }
}

所以这题bfs写法如下

#include<bits/stdc++.h> 
using namespace std;
struct pp
{
    int x,y;
};
deque<pp> q;//队列 
int n,m,ans=0;//n行m列，ans为答案 
int a[105][105];//存矩阵 
bool used[105][105];//记录是否走过 
int dx[4]={-1,1,0,0};//向上下左右走一步行号和列好的改变 
int dy[4]={0,0,-1,1};
void bfs(int sx,int sy)//bfs 
{
    pp st;
    st.x=sx;st.y=sy;
    used[sx][sy]=1;
    q.push_back(st);
    while(!q.empty())
    {
        pp nw=q.front();
        for(int i=0;i<4;i++)
        {
            pp nxt=nw;
            nxt.x+=dx[i];
            nxt.y+=dy[i];
            if(a[nxt.x][nxt.y]==0 || used[nxt.x][nxt.y]==1) continue;
            used[nxt.x][nxt.y]=1;//把这一连通块的点染色 
            q.push_back(nxt);
        }
        q.pop_front();
    }
}
int main()
{
    cin>>n>>m;
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            scanf("%1d",&a[i][j]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(used[i][j]==0 && a[i][j]!=0)
            {
                bfs(i,j);
                ans++;//若这一连通块没搜过ans++ 
            }
        }
    }
    cout<<ans;  
    return 0;
}

那dfs呢 dfs是一次走到底，然后回溯

/*
void dfs()
{
    for(拓展状态)
    {
        判断合法
        记录
        dfs(继续搜);
        回溯;
    }
}
*/

所以这题dfs代码

#include<bits/stdc++.h> 
using namespace std;
int n,m,ans=0;
int a[105][105];
bool used[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y)
{
    used[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(a[nx][ny]==0 || used[nx][ny]==1) continue;
        dfs(nx,ny);
    }
}
int main()
{
    cin>>n>>m;
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            scanf("%1d",&a[i][j]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(used[i][j]==0 && a[i][j]!=0)
            {
                dfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans;  
    return 0;
}

拜拜