2024/1/17 DFS BFS + Div 3 a,b

目录

Lake Counting S

求细胞数量

海战?

组合的输出

div3?A. Square

div3?B. Arranging Cats

---

Lake Counting S

P1596 [USACO10OCT] Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

感谢大佬的指点！！！！

思路：用bfs，遇到w就进入bfs一次，把搜索到的w全部变成 .?,然后ans++

最后答案输出（其实就是看进入了几次bfs)

中途re了一次，因为int bfs(int x,int y)没有写返回值，把int 改成void就行了

re的原因：越界或者递归没有出口

?

完整代码

#include <bits/stdc++.h>
const int N = 110;
char g[N][N];
bool vis[N][N]{};
int n,m,ans;
struct node
{
    int r,c;
};
int rr[10]={-1,1,0,0,-1,1,-1,1};
int cc[10]={0,0,-1,1,-1,-1,1,1};
void bfs(int x,int y)
{
    std::queue<node> q;
    q.push({x,y});
    while(!q.empty())
    {
        node tmp=q.front();
        q.pop();
        int cur_r=tmp.r,cur_c=tmp.c;
        for(int i = 0;i < 8;i ++)
        {
            int next_r=cur_r+rr[i];
            int next_c=cur_c+cc[i];
            if(next_r>=1&&next_r<=n&&next_c>=1&&next_c<=m&&vis[next_r][next_c]==false&&g[next_r][next_c]=='W')
            {
                q.push({next_r,next_c});
                g[next_r][next_c]='.';
                vis[next_r][next_c]=true;
            }
        }
    }
}
int main()
{
    std::cin >> n >> m;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            std::cin >> g[i][j];
        }
    }
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            if(g[i][j]=='W')
            {
                bfs(i,j);
                ans++;
            }
        }
    }
    std::cout<<ans<<"\n";
    return 0;
}

求细胞数量

P1451 求细胞数量 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题和前面那一道是同一个类型的，搜索的方向又八个减少到了四个，思路也差不多，遇到数字细胞就进入一次bfs，,把上下左右的数字细胞全部置为零，然后ans++，最后输出答案

完整代码

#include <bits/stdc++.h>
const int N = 110;
int g[N][N];
bool vis[N][N]{};
int rr[4]={-1,1,0,0};
int cc[4]={0,0,-1,1};
int n,m,ans;
struct node
{
    int r,c;
};
void bfs(int x,int y)
{
    std::queue<node> q;
    q.push({x,y});
    while(!q.empty())
    {
        node tmp=q.front();
        q.pop();
        int cur_r=tmp.r,cur_c=tmp.c;
        for(int i = 0;i < 4;i ++)
        {
            int next_r=cur_r+rr[i];
            int next_c=cur_c+cc[i];
            if(next_r>=1&&next_r<=n&&next_c>=1&&next_c<=m&&g[next_r][next_c]!=0&&vis[next_r][next_c]==false)
            {
                q.push({next_r,next_c});
                vis[next_r][next_c]=true;
                g[next_r][next_c]=0;
            }
        }
    }
}
int main()
{
    std::cin >> n >> m;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            scanf("%1d",&g[i][j]);
        }
    }
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            if(g[i][j]>=1&&g[i][j]<=9)
            {
                bfs(i,j);
                ans++;
            }
        }
    }
    std::cout<<ans<<"\n";
    return 0;
}

海战?

P1331 海战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题和上面两个大体相似，只是多了一个判断，用的算法还是bfs

当船是这样的时候，就会发生碰撞

先进行一个判断，如果发生碰撞就输出Bad placement.然后直接结束return（注意在判断的时候不要越界，循环里面的num要及时清空，不然一直会累加）

如果没有发生碰撞，就进入bfs进行搜索看一共有几艘船

完整代码

?

#include <bits/stdc++.h>
const int N = 1010;
struct node
{
    int r,c;
};
int rr[4]={-1,1,0,0};
int cc[4]={0,0,-1,1};
char g[N][N];
bool vis[N][N]{};
int n,m,ans;
int num;
void bfs(int x,int y)
{
    std::queue<node> q;
    q.push({x,y});
    while(!q.empty())
    {
        node tmp=q.front();
        q.pop();
        int cur_r=tmp.r,cur_c=tmp.c;
        int j=0;
        for(int i = 0;i < 4;i ++)
        {
            int next_r=cur_r+rr[i];
            int next_c=cur_c+cc[i];
            if(next_r>=1&&next_r<=n&&next_c>=1&&next_c<=m&&g[next_r][next_c]=='#'&&vis[next_r][next_c]==false)
            {
                q.push({next_r,next_c});
                g[next_r][next_c]='.';
                vis[next_r][next_c]=true;
                j++;
            }
        }
    }
}
int main()
{
    std::cin >> n >> m;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            std::cin >> g[i][j];
        }
    }
    for(int i = 1;i < n;i ++)
    {
        for(int j = 1;j < m;j ++)
        {
            if(g[i][j]=='#')
                num++;
            if(g[i][j+1]=='#')
                num++;
            if(g[i+1][j]=='#')
                num++;
            if(g[i+1][j+1]=='#')
                num++;
            if(num==3)
            {
                printf("Bad placement.");
                return 0;
            }
            num=0;
        }
    }
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            if(g[i][j]=='#')
            {
                bfs(i,j);
                ans++;
            }
        }
    }

    printf("There are %d ships.",ans);
    return 0;
}

?

组合的输出

P1157 组合的输出 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题使用dfs，就是全排列的变形，但是核心代码那里可以精简很多

完整代码

#include <bits/stdc++.h>
const int N = 110;
int n,m;
//int state[N];
int path[N];//存数
void dfs(int u)
{
    if(u>m)
    {
        for(int i = 1;i <= m;i ++)
        {
            std::cout<<std::setw(3)<<path[i];//场宽为3
        }
        std::cout<<"\n";
    }
    else
    {
        for(int i = path[u-1]+1;i <= n;i ++)
        {
            path[u]=i;
            dfs(u+1);
        }
    }
}
int main()
{
    std::cin >> n >> m;
    dfs(1);
    return 0;
}

div3?A. Square

Problem - A - Codeforces

方法：暴力

完整代码

#include <bits/stdc++.h>
#define int long long
const int N = 10086;
int x[N];
int y[N];
signed main()
{
    int t;
    std::cin >> t;
    while(t --)
    {
        int maxx=-999999,minx=999999,maxy=-9999999,miny=9999999;
        for(int i = 1;i <= 4;i ++)
        {
            std::cin >> x[i] >> y[i];
            maxx=std::max(maxx,x[i]);
            minx=std::min(minx,x[i]);
            maxy=std::max(maxy,y[i]);
            miny=std::min(miny,y[i]);
        }
        int ans=(maxx-minx)*(maxy-miny);
        std::cout<<ans<<"\n";
    }
    return 0;
}

div3?B. Arranging Cats

Problem - B - Codeforces

这道题其实就是输出 需要移动的1+需要删除的1?? ?

两个变量a1,b1,用来记录出现的不相同的位置的1，

两排字符串作比较，如果不相同，那么在字符串为1对应的变量那里++（如果是第一排有1，那么a1++,如果第二排有1，那么b1++）

完整代码

#include <bits/stdc++.h>
#define int long long
const int N = 1e5+10;
int a[N],b[N];
int a1,b1;
int mov1;
int delete1;
signed main()
{
    int t;
    std::cin >> t;
    while(t --)
    {
        int n;
        std::cin >> n;
        for(int i = 1;i <= n;i ++)
        {
            scanf("%1d",&a[i]);
        }
        for(int i = 1;i <= n;i ++)
        {
            scanf("%1d",&b[i]);
        }
        for(int i = 1;i <= n;i ++)
        {
            if(a[i]!=b[i])
            {
                if(a[i]==1)
                    a1++;
                else if(b[i]==1)
                    b1++;
            }
        }
        mov1=std::min(a1,b1);
        delete1=std::abs(a1-b1);
        std::cout<<mov1+delete1<<"\n";
        a1=0,b1=0;
    }
    return 0;
}