头像

秋天寒

东南大学




离线:8小时前


最近来访(13)
用户头像
小阿徐
用户头像
σ.
用户头像
violet_garden
用户头像
KaYeungLam
用户头像
tianming
用户头像
风不会停息_6
用户头像
白露
用户头像
coder_6
用户头像
White55kai
用户头像
plokmnjiu
用户头像
阳ing
用户头像
理塘丁真_
用户头像
Rorschach_5


矩阵距离

本题为多源bfs问题,bfs的大部分过程都一样,不一样的是把初始节点放进去的时候,需要把每个源头节点都放进去

#include<iostream>
#include<cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;

const int N=1010;
char g[N][N];
int dist[N][N];
pii q[N*N];
int n,m;

void bfs(){
    int dx[4]={-1,0,1,0};
    int dy[4]={0,1,0,-1};

    int hh=0,tt=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='0'){
                dist[i][j]=-1;
            }
            else{
                dist[i][j]=0;
                q[++tt]={i,j};
            }
        }
    }

    while(hh<=tt){
        pii t=q[hh++];
        for(int i=0;i<4;i++){
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m)continue;
            if(g[a][b]=='1'||dist[a][b]!=-1)continue;
            q[++tt]={a,b};
            dist[a][b]=dist[t.x][t.y]+1;
        }
    }


}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>g[i];
    bfs();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++){
            cout<<dist[i][j]<<" ";
        }
        cout<<endl;
    }
}


活动打卡代码 AcWing 173. 矩阵距离

#include<iostream>
#include<cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;

const int N=1010;
char g[N][N];
int dist[N][N];
pii q[N*N];
int n,m;

void bfs(){
    int dx[4]={-1,0,1,0};
    int dy[4]={0,1,0,-1};

    int hh=0,tt=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='0'){
                dist[i][j]=-1;
            }
            else{
                dist[i][j]=0;
                q[++tt]={i,j};
            }
        }
    }

    while(hh<=tt){
        pii t=q[hh++];
        for(int i=0;i<4;i++){
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m)continue;
            if(g[a][b]=='1'||dist[a][b]!=-1)continue;
            q[++tt]={a,b};
            dist[a][b]=dist[t.x][t.y]+1;
        }
    }


}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>g[i];
    bfs();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++){
            cout<<dist[i][j]<<" ";
        }
        cout<<endl;
    }
}



抓住那头牛

本题bfs思路比较简单,主要是要想清楚数据范围:

  • 首先每次一步有三种可能,分别是1,-1,x三种可能,所以如果n本来已经大于N的话就不会再跳两倍了,因为跳两倍需要一步一步走回来,显然是亏的
  • 同样的道理,无法走到负数,因为走到负数还需要每次一步一步走回来,所以干脆直接不走出去是最赚的

下面是代码

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

const int N=1e5+10;
int n,k;
int q[N];
int dist[N];

int bfs(){
    memset(dist,-1,sizeof dist);
    int hh=0,tt=-1;
    q[++tt]=n;
    dist[n]=0;
    while(hh<=tt){
        int t=q[hh++];
        if(t==k)return dist[t];
        if(t+1<N&&dist[t+1]==-1){
            q[++tt]=t+1;
            dist[t+1]=dist[t]+1;
        }
        if(t-1>=0&&dist[t-1]==-1){
            q[++tt]=t-1;
            dist[t-1]=dist[t]+1;
        }
        if(t*2<N&&dist[t*2]==-1){
            q[++tt]=t*2;
            dist[t*2]=dist[t]+1;
        }
    }
    return -1;

}

int main(){
    cin>>n>>k;
    cout<<bfs();
    return 0;
}


活动打卡代码 AcWing 1100. 抓住那头牛

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

const int N=1e5+10;
int n,k;
int q[N];
int dist[N];

int bfs(){
    memset(dist,-1,sizeof dist);
    int hh=0,tt=-1;
    q[++tt]=n;
    dist[n]=0;
    while(hh<=tt){
        int t=q[hh++];
        if(t==k)return dist[t];
        if(t+1<N&&dist[t+1]==-1){
            q[++tt]=t+1;
            dist[t+1]=dist[t]+1;
        }
        if(t-1>=0&&dist[t-1]==-1){
            q[++tt]=t-1;
            dist[t-1]=dist[t]+1;
        }
        if(t*2<N&&dist[t*2]==-1){
            q[++tt]=t*2;
            dist[t*2]=dist[t]+1;
        }
    }
    return -1;

}

int main(){
    cin>>n>>k;
    cout<<bfs();
    return 0;
}



武士风度的牛

本题为bfs的题,下面说一下该题的特殊之处:

  • 本题向前走的方式不同,本题是向前走日字,但是只需要在处理dx和dy的时候做变化即可
  • 本题需要维护一个dist数组,每次遍历到一个合理的点,就用前一个点的dis+1来更新该点

下面是代码

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

#define x first
#define y second
typedef pair<int,int> pii;

const int N=160;
pii q[N*N];
char g[N][N];
int dist[N][N];
int n,m;

int bfs(){
    int dx[8]={-2,-1,1,2,2,1,-1,-2};
    int dy[8]={1,2,2,1,-1,-2,-2,-1};
    int hh=0,tt=-1;
    memset(dist,-1,sizeof dist);
    int sx=0,sy=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(g[i][j]=='K'){
                sx=i,sy=j;
                break;
            }
        }

    q[++tt]={sx,sy};
    dist[sx][sy]=0;
    while(hh<=tt){
        pii t=q[hh++];
        for(int i=0;i<8;i++){
            int a=t.x+dx[i];
            int b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m)continue;
            if(dist[a][b]!=-1)continue;
            if(g[a][b]=='*')continue;

            q[++tt]={a,b};
            dist[a][b]=dist[t.x][t.y]+1;
        }
    }

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(g[i][j]=='H'){
                return dist[i][j];
            }
        }
}

int main(){
    cin>>m>>n;
    for(int i=0;i<n;i++)cin>>g[i];
    int d=bfs();
    cout<<d;
    return 0;
}


活动打卡代码 AcWing 188. 武士风度的牛

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

#define x first
#define y second
typedef pair<int,int> pii;

const int N=160;
pii q[N*N];
char g[N][N];
int dist[N][N];
int n,m;

int bfs(){
    int dx[8]={-2,-1,1,2,2,1,-1,-2};
    int dy[8]={1,2,2,1,-1,-2,-2,-1};
    int hh=0,tt=-1;
    memset(dist,-1,sizeof dist);
    int sx=0,sy=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(g[i][j]=='K'){
                sx=i,sy=j;
                break;
            }
        }

    q[++tt]={sx,sy};
    dist[sx][sy]=0;
    while(hh<=tt){
        pii t=q[hh++];
        for(int i=0;i<8;i++){
            int a=t.x+dx[i];
            int b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m)continue;
            if(dist[a][b]!=-1)continue;
            if(g[a][b]=='*')continue;

            q[++tt]={a,b};
            dist[a][b]=dist[t.x][t.y]+1;
        }
    }

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(g[i][j]=='H'){
                return dist[i][j];
            }
        }
}

int main(){
    cin>>m>>n;
    for(int i=0;i<n;i++)cin>>g[i];
    int d=bfs();
    cout<<d;
    return 0;
}



迷宫问题

本题的特殊之处在于,本题需要输出方案,输出方案的方法:

  • 把本来用于标记该点是否被遍历过的st数组改为pre数组用于存储上一个节点的下标。所以只需要在bfs结束之后从最后遍历到最前面,每次输出当前节点下标,再用pre数组里的值去更新节点。
  • 棋盘类型的pre数组存的是pii类型
  • 找路径更新节点时,不能把横坐标和纵坐标分开更新,应该一起更新,否则更新第二个坐标的时候会出问题,详细见注释

下面是代码

#include<iostream>
#include<cstring>

using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;

const int N = 1010;
pii last[N][N];
int g[N][N];
pii q[N*N];
int n;

void bfs(){
    int dx[4]={-1,0,1,0};
    int dy[4]={0,1,0,-1};

    int hh=0,tt=-1;
    q[++tt]={n-1,n-1};
    memset(last,-1,sizeof last);
    last[n-1][n-1]={0,0};

    while(hh<=tt){
        pii t=q[hh++];
        for(int i=0;i<4;i++){
            int kx=t.x+dx[i];
            int ky=t.y+dy[i];
            if(kx<0||kx>=n||ky<0||ky>=n)continue;
            if(g[kx][ky])continue;
            if(last[kx][ky].x!=-1)continue;
            q[++tt]={kx,ky};
            last[kx][ky]={t.x,t.y};
        }
    }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];

    bfs();
    pii end(0, 0);
    while (true)
    {
        printf("%d %d\n", end.x, end.y);
        if (end.x == n - 1 && end.y == n - 1) break;
        end = last[end.x][end.y];//如果end.x和end.y分两步赋值就会出问题
    }



}


活动打卡代码 AcWing 1076. 迷宫问题

#include<iostream>
#include<cstring>

using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;

const int N = 1010;
pii last[N][N];
int g[N][N];
pii q[N*N];
int n;

void bfs(){
    int dx[4]={-1,0,1,0};
    int dy[4]={0,1,0,-1};

    int hh=0,tt=-1;
    q[++tt]={n-1,n-1};
    memset(last,-1,sizeof last);
    last[n-1][n-1]={0,0};

    while(hh<=tt){
        pii t=q[hh++];
        for(int i=0;i<4;i++){
            int kx=t.x+dx[i];
            int ky=t.y+dy[i];
            if(kx<0||kx>=n||ky<0||ky>=n)continue;
            if(g[kx][ky])continue;
            if(last[kx][ky].x!=-1)continue;
            q[++tt]={kx,ky};
            last[kx][ky]={t.x,t.y};
        }
    }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];

    bfs();
    pii end(0, 0);
    while (true)
    {
        printf("%d %d\n", end.x, end.y);
        if (end.x == n - 1 && end.y == n - 1) break;
        end = last[end.x][end.y];//如果end.x和end.y分两步赋值就会出问题
    }



}



山峰和山谷

属于bfs的floodfill模型,和前面题的相同之处在于代码结构一样,但是本题维护的变量不同,本题需要维护边界关系的量,需要用用bfs函数引用传出

#include<iostream>
using namespace std;

const int N=1010;
#define x first
#define y second
typedef pair<int,int> pii;
int g[N][N];
bool st[N][N];
pii q[N*N];
int n;

void bfs(int sx,int sy,bool &has_higher,bool &has_lower){
    int hh=0,tt=-1;
    q[++tt]={sx,sy};
    st[sx][sy]=true;
    while(hh<=tt){
        pii t=q[hh++];
        for(int i=t.x-1;i<=t.x+1;i++)
            for(int j=t.y-1;j<=t.y+1;j++){
                if(i==t.x&&j==t.y)continue;
                if(i<0||i>=n||j<0||j>=n)continue;
                if(g[i][j]!=g[t.x][t.y]){
                    if(g[i][j]>g[t.x][t.y])has_higher=true;
                    if(g[i][j]<g[t.x][t.y])has_lower=true;
                }
                else if(!st[i][j]){
                    q[++tt]={i,j};
                    st[i][j]=true;
                }
            }
    }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];
    int cnth=0, cntl=0;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(st[i][j])continue;
            bool has_higher=false,has_lower=false;
            bfs(i,j,has_higher,has_lower);
            if(!has_higher)cntl++;
            if(!has_lower)cnth++;
        }

    cout<<cntl<<" "<<cnth;
    return 0;
}


活动打卡代码 AcWing 1106. 山峰和山谷

#include<iostream>
using namespace std;

const int N=1010;
#define x first
#define y second
typedef pair<int,int> pii;
int g[N][N];
bool st[N][N];
pii q[N*N];
int n;

void bfs(int sx,int sy,bool &has_higher,bool &has_lower){
    int hh=0,tt=-1;
    q[++tt]={sx,sy};
    st[sx][sy]=true;
    while(hh<=tt){
        pii t=q[hh++];
        for(int i=t.x-1;i<=t.x+1;i++)
            for(int j=t.y-1;j<=t.y+1;j++){
                if(i==t.x&&j==t.y)continue;
                if(i<0||i>=n||j<0||j>=n)continue;
                if(g[i][j]!=g[t.x][t.y]){
                    if(g[i][j]>g[t.x][t.y])has_higher=true;
                    if(g[i][j]<g[t.x][t.y])has_lower=true;
                }
                else if(!st[i][j]){
                    q[++tt]={i,j};
                    st[i][j]=true;
                }
            }
    }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];
    int cnth=0, cntl=0;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(st[i][j])continue;
            bool has_higher=false,has_lower=false;
            bfs(i,j,has_higher,has_lower);
            if(!has_higher)cntl++;
            if(!has_lower)cnth++;
        }

    cout<<cntl<<" "<<cnth;
    return 0;
}