池塘计数(bfs)

农夫约翰有一片 N∗M 的矩形土地。

最近,由于降雨的原因,部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内,如果包含雨水,则用”W”表示,如果不含雨水,则用”.”表示。

现在,约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘,即矩阵中共有多少片相连的”W”块。

输入格式
第一行包含两个整数 N 和 M。

接下来 N 行,每行包含 M 个字符,字符为”W”或”.”,用以表示矩形土地的积水状况,字符之间没有空格。

输出格式
输出一个整数,表示池塘数目。

数据范围
1≤N,M≤1000
输入样例:
10 12
W…WW.
.WWW…WWW
…WW…WW.
…WW.
…W…
…W…W…
.W.W…WW.
W.W.W…W.
.W.W…W.
…W…W.
输出样例:
3

#include<iostream>
#include<queue>
using namespace std;

const int N = 1010;
char a[N][N];
int n,m,v[N][N],ans=0;
queue<pair<int,int>> q;

void bfs(int x,int y)
{
    
    q.push({x,y}); 
    v[x][y]=true;
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        for(int i=t.first-1;i<=t.first+1;i++)
        {
            for(int j=t.second-1;j<=t.second+1;j++)
            {
                if(i==t.first&&j==t.second) continue;
                if(i<0||i>=n||j<0||j>=m) continue;
                if(a[i][j]!='W'||v[i][j]) continue;
                v[i][j]=true;
                q.push({i,j});
            }
        }
    }
}

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]=='W'&&!v[i][j])
            {
                bfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

池塘计数(dfs)

#include<iostream>
#include<queue>
using namespace std;

const int N = 1010;
char a[N][N];
int n,m,v[N][N],ans=0;
queue<pair<int,int>> q;

void dfs(int x,int y)
{
    if(x<0||x>=n||y<0||y>=m) return ;
    if(a[x][y]!='W') return;
    a[x][y]='.';
    dfs(x-1,y-1);
    dfs(x-1,y);
    dfs(x-1,y+1);
    dfs(x,y-1);
    dfs(x,y+1);
    dfs(x+1,y-1);
    dfs(x+1,y);
    dfs(x+1,y+1);
}

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]=='W')
            {
                dfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

迷宫问题

给定一个 n×n 的二维数组,如下所示:

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

输入格式
第一行包含整数 n。

接下来 n 行,每行包含 n 个整数 0 或 1,表示迷宫。

输出格式
输出从左上角到右下角的最短路线,如果答案不唯一,输出任意一条路径均可。

按顺序,每行输出一个路径中经过的单元格的坐标,左上角坐标为 (0,0),右下角坐标为 (n−1,n−1)。

数据范围
0≤n≤1000
输入样例:
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例:
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

#include<iostream>
#include<queue>
using namespace std;

const int N = 1010;
int n;
queue<pair<int,int>> q;
pair<int,int> pre[N][N];
int a[N][N],v[N][N];
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};

void bfs(int x,int y)
{
    q.push({x,y});
    pre[x][y]={0,0};
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            if(x<0||x>=n||y<0||y>=n) continue;
            if(a[x][y]==1||v[x][y]==true) continue;
            v[x][y]=true;
            q.push({x,y});
            pre[x][y]=t;
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>a[i][j];
        }
    }
    
    bfs(n-1,n-1);
    pair<int,int> t(0,0);
    
    while(1)
    {
        cout<<t.first<<" "<<t.second<<endl;
        if(t.first==n-1&&t.second==n-1) break;
        t=pre[t.first][t.second];
    }
    
}

武士风度的牛

农民 John 有很多牛,他想交易其中一头被 Don 称为 The Knight 的牛。

这头牛有一个独一无二的超能力,在农场里像 Knight 一样地跳(就是我们熟悉的象棋中马的走法)。

虽然这头神奇的牛不能跳到树上和石头上,但是它可以在牧场上随意跳,我们把牧场用一个 x,y 的坐标图来表示。

这头神奇的牛像其它牛一样喜欢吃草,给你一张地图,上面标注了 The Knight 的开始位置,树、灌木、石头以及其它障碍的位置,除此之外还有一捆草。

现在你的任务是,确定 The Knight 要想吃到草,至少需要跳多少次。

The Knight 的位置用 K 来标记,障碍的位置用 * 来标记,草的位置用 H 来标记。

这里有一个地图的例子:

         11 | . . . . . . . . . .
         10 | . . . . * . . . . . 
          9 | . . . . . . . . . . 
          8 | . . . * . * . . . . 
          7 | . . . . . . . * . . 
          6 | . . * . . * . . . H 
          5 | * . . . . . . . . . 
          4 | . . . * . . . * . . 
          3 | . K . . . . . . . . 
          2 | . . . * . . . . . * 
          1 | . . * . . . . * . . 
          0 ----------------------
                                1 
            0 1 2 3 4 5 6 7 8 9 0 

The Knight 可以按照下图中的 A,B,C,D… 这条路径用 5 次跳到草的地方(有可能其它路线的长度也是 5):

         11 | . . . . . . . . . .
         10 | . . . . * . . . . .
          9 | . . . . . . . . . .
          8 | . . . * . * . . . .
          7 | . . . . . . . * . .
          6 | . . * . . * . . . F<
          5 | * . B . . . . . . .
          4 | . . . * C . . * E .
          3 | .>A . . . . D . . .
          2 | . . . * . . . . . *
          1 | . . * . . . . * . .
          0 ----------------------
                                1
            0 1 2 3 4 5 6 7 8 9 0

注意: 数据保证一定有解。

输入格式
第 1 行: 两个数,表示农场的列数 C 和行数 R。

第 2…R+1 行: 每行一个由 C 个字符组成的字符串,共同描绘出牧场地图。

输出格式
一个整数,表示跳跃的最小次数。

数据范围
1≤R,C≤150
输入样例:
10 11



.

…H


.K…
…*

输出样例:
5

#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;

const int N = 200;
queue<pair<int,int>> q;
char a[N][N];
int d[N][N],v[N][N];
int n,m;
int dx[]={1,2,2,1,-1,-2,-2,-1},dy[]={2,1,-1,-2,2,1,-1,-2};

int bfs(int x,int y)
{
    q.push({x,y});
    v[x][y]=true;
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            int x=t.first+dx[i],y=t.second+dy[i];
            if(x<0||x>=n||y<0||y>=m) continue;
            if(v[x][y]) continue;
            if(a[x][y]=='*') continue;
            if(a[x][y]=='H') return d[t.first][t.second]+1;
            
            d[x][y]=d[t.first][t.second]+1;
            v[x][y]=true;
            q.push({x,y});
        }
    }
    return 0;
}

int main()
{
    cin>>m>>n;
    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]=='K')
            {
                cout<<bfs(i,j);
                return 0;
            }
        }
    }   
}

抓住那头牛

农夫知道一头牛的位置,想要抓住它。

农夫和牛都位于数轴上,农夫起始位于点 N,牛位于点 K。

农夫有两种移动方式:

从 X 移动到 X−1 或 X+1,每次移动花费一分钟
从 X 移动到 2∗X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。

农夫最少要花多少时间才能抓住牛?

输入格式
共一行,包含两个整数N和K。

输出格式
输出一个整数,表示抓到牛所花费的最少时间。

数据范围
0≤N,K≤105
输入样例:
5 17
输出样例:
4

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 200007;
int d[N],v[N],n,m;
queue<int> q;
int dfs()
{
    q.push(n);
    v[n]=true;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        if(t+1<N&&v[t+1]==false)
        {
            d[t+1]=d[t]+1;
            v[t+1]=true;
            q.push(t+1);
        }
        if(t-1>=0&&v[t-1]==false)
        {
            d[t-1]=d[t]+1;
            v[t-1]=true;
            q.push(t-1);
        }
        if(2*t<N&&v[2*t]==false)
        {
            d[2*t]=d[t]+1;
            v[2*t]=true;
            q.push(2*t);
        }
        if(t==m) return d[t];
    }
    return -1;
}

int main()
{
    cin>>n>>m;
    cout<<dfs();
}

填充颜色

image-1649814355372

#include<bits/stdc++.h>
using namespace std;
const int N=1000;


int n,m,v[N][N];
int a[N][N];
queue<pair<int,int>> q;
int ans=0;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};

void bfs(int x,int y)
{
    q.push({x,y});
    v[x][y]=true;
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            if(a[x][y]==0)  //先特判自己是不是0
            {
                a[x][y]=2;
                v[x][y]=true;
                q.push({x,y});
            }   
            //再特判自己的上下左右
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            if(x<0||x>=n||y<0||y>=m) continue;
            if(v[x][y]||a[x][y]!=0) continue;
            if(a[x][y]==0)
            {
                a[x][y]=2;
                v[x][y]=true;
                q.push({x,y});
            }
        }
    }
}

int main()
{
    cin>>n;
    m=n;
    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]==1)
            {
                bfs(i+1,j+1);   //如果当前为1,则从1的右下角开始遍历
                                //因为只有一个闭环,所以出来就打印返回
                for(int p=0;p<n;p++)
                {
                    for(int q=0;q<m;q++)
                    {
                        cout<<a[p][q]<<" ";
                    }
                    cout<<endl;
                }
                return 0;
            }
        }
    }   
}

拯救oibh总部(边界注水)

image-1649814334904

思路:

从四个边界注水,如果被淹到了就设置为1,最后遍历剩余0的数量即可

住:不可以对所有数据进行bfs,会把所有0变成1

#include<bits/stdc++.h>
using namespace std;
const int N=1000;


int n,m,v[N][N];
char a[N][N];
queue<pair<int,int>> q;
int ans=0;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};

void bfs(int x,int y)
{
    q.push({x,y});
    v[x][y]=true;
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)	
        {
            if(a[x][y]=='0')	//自我判断
            {
                v[x][y]=true;
                a[x][y]='1';
                q.push({x,y});
            }
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            if(x<0||x>=n||y<0||y>=m) continue;
            if(v[x][y]||a[x][y]!='0') continue;
            v[x][y]=true;
            a[x][y]='1';
            q.push({x,y});
        }
    }
}

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 j=0;j<m;j++)		//从上下边界注水
    {
        if(a[0][j]=='0'&&!v[0][j]) bfs(0,j);
        if(a[n-1][j]=='0'&&!v[n-1][j]) bfs(n-1,j);
    }
    for(int i=0;i<n;i++)		//从左右边界注水
    {
        if(a[i][0]=='0'&&!v[i][0]) bfs(i,0);
        if(a[i][m-1]=='0'&&!v[i][m-1]) bfs(i,m-1);
    }


    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]=='0') ans++;
        }
    }
    cout<<ans;
}

矩阵距离(多源bfs)

给定一个 N 行 M 列的 01 矩阵 A,A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为:

dist(A[i][j],A[k][l])=|i−k|+|j−l|
输出一个 N 行 M 列的整数矩阵 B,其中:

B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])
输入格式
第一行两个整数 N,M。

接下来一个 N 行 M 列的 01 矩阵,数字之间没有空格。

输出格式
一个 N 行 M 列的矩阵 B,相邻两个整数之间用一个空格隔开。

数据范围
1≤N,M≤1000
输入样例:
3 4
0001
0011
0110
输出样例:
3 2 1 0
2 1 0 0
1 0 0 1

#include<iostream>
using namespace std;
#include<cstring>
#include<queue>

const int N = 1010;
int n,m,d[N][N],a[N][N],v[N][N];
queue<pair<int,int>> q;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};


void bfs()
{
    while(!q.empty())
    {
        auto  t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i],y=t.second+dy[i];
            if(x<0||x>=n||y<0||y>=m) continue;
            if(v[x][y]) continue;
            q.push({x,y});
            d[x][y]=d[t.first][t.second]+1;
            v[x][y]=true;
        }
    }
    
}

int main()
{
    cin>>n>>m;
    memset(d,-1,sizeof(d));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            char c;
            cin>>c;
            if(c=='1') 
            {
                a[i][j]=c-'0';
                v[i][j]=true;
                d[i][j]=0;
                q.push({i,j});
            }
            else 
            {
                a[i][j]=c-'0';
            }
        }
    }
    
   bfs();
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cout<<d[i][j]<<" ";
        }
        cout<<endl;
    }
}

血色先锋队(曼哈顿距离)

image-1650026332923

img

#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int n,k,m,ans,sum;

int ax[N],ay[N],bx,by;

int main()
{
    cin>>n>>m;
    int a,b;
    cin>>a>>b;
    for(int i=0;i<a;i++)
    {
        cin>>ax[i]>>ay[i];
    }
    
    while(b--)
    {
        cin>>bx>>by;
        ans=0x3f3f3f3f;
        for(int i=0;i<a;i++)
        {
            ans=min(ans,abs(ax[i]-bx)+abs(ay[i]-by));
        }
        cout<<ans<<endl;
    }
}

Cow Picnic S(图的bfs)

image-1650026323148

#include<bits/stdc++.h>
using namespace std;
const int N=10000;
int n,k,m,ans,sum[N];	//sum[i]表示i号牧场有多少牛可以到达
int v[N];
queue<int> q;
int st[N]; 			//牛所在牧场编号
int head[N],to[N],w[N],nxt[N],i=0;
void add(int a,int b,int c)
{
    to[i]=b;
    w[i]=c;
    nxt[i]=head[a];
    head[a]=i++;
}

void bfs(int k)     //k为牧场号
{
    q.push(k);
    v[k]=true;
    while(!q.empty())
    {
        int t=q.front();    
        q.pop();
        for(int i=head[t];i!=-1;i=nxt[i])
        {
            int j=to[i];    //j为当前牧场的下一个牧场号
            if(!v[j])
            {
                q.push(j);
                sum[j]++;
                v[j]=true;
            }
        }
    }
}

int main()
{
    cin>>k>>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=k;i++)
    {
        cin>>st[i];
        sum[st[i]]++;
    }

    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y,1);
    }

    for(int i=1;i<=k;i++)
    {
        memset(v,0,sizeof(v));		//对所有牛进行扩展,找出能到的牧场数
        bfs(st[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(sum[i]==k) ans++;	//如果当前牧场可到的牛的数量等于所有牛
    }								//说明所有牛都可以到,答案+
    cout<<ans;

}

Q.E.D.