算法总结--广搜进阶1

feizhu_QWQ · 2024-08-01 13:48:04 · 算法·理论

(｡･∀･)ﾉﾞ嗨飞竹小课堂第21课开课喽!
咳咳，BFS走起！
离开中山路
这道题就是明显且经典简单的广搜，什么也不讲QWQ
cows
咳咳，这道题就是经典的记录路径，有tow种方法，第一个是pre数组，记录每个点的上一个点是哪个点，最后写一个print来输出，运用递归原理，完事
另一种就是在队列里面放一个vector，而且不是一般的容易MLE
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
char a[1005][1005];
bool vis[1005][1005];
int head=0,tail=1;
struct node
{
    int x,y;
}q[1000005];
node pre[1005][1005];
bool check(int x,int y)
{
    if(x<1||x>n||y<1||y>m||vis[x][y]==true) return false;
    else return true;
}
void print(int x,int y)
{
    if(x==-1&&y==-1)
    {
        return;
    }
    print(pre[x][y].x,pre[x][y].y);
    cout<<x<<" "<<y<<endl;
}
void work(int x,int y,int fx,int fy)
{
    if(check(x,y)==true)
    {
        head++;
        q[head].x=x;
        q[head].y=y;
        pre[x][y].x=fx;
        pre[x][y].y=fy;
        vis[x][y]=true;
        if(x==n&&y==m)
        {
            print(x,y);
            exit(0);
        }
    }
}
void bfs()
{
    head++;
    q[head].x=1;
    q[head].y=1;
    vis[1][1]=true;
    pre[1][1].x=-1;
    pre[1][1].y=-1;
    while(head-tail+1>0)
    {
        int x=q[tail].x;
        int y=q[tail].y;
        tail++;
        work(x-1,y,x,y);
        work(x+1,y,x,y);
        work(x,y-1,x,y);
        work(x,y+1,x,y);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='*') vis[i][j]=true;
        }
    }
    bfs();
    return 0;
}

找机厅
这道题也是记录路径，这个LRUD在print函数里改一下就好了，我数组开小了QWQ

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
char a[2005][2005];
bool vis[2005][2005];
int head=0,tail=1;
struct node
{
    int x,y,step;
}q[4000005];
node pre[2005][2005];
bool check(int x,int y)
{
    if(x<1||x>n||y<1||y>m||vis[x][y]==true) return false;
    else return true; 
}
void print(int x,int y,int fx,int fy)
{
    if(x==-1&&y==-1) return;
    print(pre[x][y].x,pre[x][y].y,x,y);
    if(x==n&&y==m) return;
    if(x-fx==1&&y-fy==0) cout<<"U";
    if(fx-x==1&&y-fy==0) cout<<"D";
    if(fx-x==0&&y-fy==1) cout<<"L";
    if(fx-x==0&&fy-y==1) cout<<"R";
}
bool work(int x,int y,int step,int fx,int fy)
{
    if(check(x,y)==true&&a[x][y]!=a[fx][fy])
    {
        head++;
        q[head].x=x;
        q[head].y=y;
        q[head].step=step;
        vis[x][y]=true;
        pre[x][y].x=fx;
        pre[x][y].y=fy;
        if(x==n&&y==m)
        {
            return true;
        }
    }
    return false;
}
int bfs()
{
    head++;
    q[head].x=1;
    q[head].y=1;
    q[head].step=0;
    pre[1][1].x=-1;
    pre[1][1].y=-1;
    vis[1][1]=true;
    while(head-tail+1>0)
    {
        int x=q[tail].x;
        int y=q[tail].y;
        int step=q[tail].step;
        tail++;
        if(work(x-1,y,step+1,x,y)==true) return step+1;
        if(work(x+1,y,step+1,x,y)==true) return step+1;
        if(work(x,y-1,step+1,x,y)==true) return step+1;
        if(work(x,y+1,step+1,x,y)==true) return step+1;
    }
    return -1;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        head=0,tail=1;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
                vis[i][j]=false;
            } 
        }
        int ans=bfs();
        if(ans==-1)
        {
            cout<<-1<<endl;
            continue;
        }
        else
        {
            cout<<ans<<endl;
            print(n,m,0,0);
            cout<<endl;
        }
    }
    return 0;
}

鬼抓人
强行建议升蓝！
这道题我们需要两个队列，一个是男生的行动，一个是女友的行动，因为鬼可以穿墙，所以我们判断会不会被鬼抓到时可以用曼哈顿距离QWQ
因为男生可以移动3步,所以我们用while循环
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
char a[1005][1005];
int n,m;
struct node
{
    int x,y;
    bool lei;
}q1[1000005];
node q2[1000005];
int head1=0,tail1=1,head2=0,tail2=0;
bool vis[1005][1005][3];
node op[5];
int sum=0;
int dis(int x_1,int y_1,int x_2,int y_2)
{
    return abs(x_2-x_1)+abs(y_2-y_1);
}
bool r_check(int x,int y,bool lei)
{
    if(a[x][y]=='X'||x<1||x>n||y<1||y>m||vis[x][y][lei]!=0) return false;
    else return true;
}
bool check(int x,int y)
{
    for(int i=1;i<=2;i++)
    {
        if(dis(x,y,op[i].x,op[i].y)<=2*sum)
        {
            return false;
        }
    }
    return true;
}
bool work1(int x,int y,bool lei)
{
    if(r_check(x,y,lei)&&check(x,y))
    {
        vis[x][y][lei]=true;
        if(vis[x][y][!lei]==true)
        {
            return true;
        }
        head1++;
        q1[head1].x=x;
        q1[head1].y=y;
        q1[head1].lei=lei;
    }
    return false;
}
bool work2(int x,int y,bool lei)
{
    if(r_check(x,y,lei)&&check(x,y))
    {
        vis[x][y][lei]=true;
        if(vis[x][y][!lei]==true)
        {
            return true;
        }
        head2++;
        q2[head2].x=x;
        q2[head2].y=y;
        q2[head2].lei=lei;
    }
    return false;
}
int bfs()
{
    while(head1-tail1+1>0&&head2-tail2+1>0)
    {
        sum++;
        int tot=3;
        while(tot--)
        {
            int len=head1-tail1+1;
            while(len--)
            {
                int x=q1[tail1].x;
                int y=q1[tail1].y;
                bool lei=q1[tail1].lei;
                tail1++;
                if(check(x,y)==false)
                {
                    continue;
                }
                if(work1(x-1,y,lei)==true) return sum;
                if(work1(x+1,y,lei)==true) return sum;
                if(work1(x,y-1,lei)==true) return sum;
                if(work1(x,y+1,lei)==true) return sum;
            }
        }
        tot=1;
        while(tot--)
        {
            int len=head2-tail2+1;
            while(len--)
            {
                int x=q2[tail2].x;
                int y=q2[tail2].y;
                bool lei=q2[tail2].lei;
                tail2++;
                if(check(x,y)==false)
                {
                    continue;
                }
                if(work2(x-1,y,lei)==true) return sum;
                if(work2(x+1,y,lei)==true) return sum;
                if(work2(x,y-1,lei)==true) return sum;
                if(work2(x,y+1,lei)==true) return sum;
            }
        }
    }
    return -1;
}
void init()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<=1;k++)
            {
                vis[i][j][k]=false;
            }
        }
    }
    sum=0;
    head1=0,tail1=1;
    head2=0,tail2=1;
    op[1].x=0,op[1].y=0;
    op[2].x=0,op[2].y=0;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        init();
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
                if(a[i][j]=='M')
                {
                    head1++;
                    q1[head1].x=i;
                    q1[head1].y=j;
                    q1[head1].lei=0;
                    vis[i][j][0]=true;
                }
                if(a[i][j]=='G')
                {
                    head2++;
                    q2[head2].x=i;
                    q2[head2].y=j;
                    q2[head2].lei=1;
                    vis[i][j][1]=true;
                }
                if(a[i][j]=='Z')
                {
                    if(op[1].x==0&&op[1].y==0)
                    {
                        op[1].x=i,op[1].y=j;
                    }
                    else
                    {
                        op[2].x=i,op[2].y=j;
                    }
                }
            }
        }
        cout<<bfs()<<endl;
    }
    return 0;
}

最后的迷宫
咳咳，老朋友
把每次能看到奖杯的地方标记，正常bfs，但要压一维：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
char a[1000005];
bool vis[1000005];
bool win[1000005];
int qx,qy,mx,my;
int head=0,tail=1;
struct node
{
    int x,y,step;
}q[10000005];
void init(int x,int y)
{
    for(int i=x;i>=1;i--)
    {
        if(a[(i-1)*m+y]=='X') break;
        win[(i-1)*m+y]=true;
    }
    for(int i=x;i<=n;i++)
    {
        if(a[(i-1)*m+y]=='X') break;
        win[(i-1)*m+y]=true;
    }
    for(int j=y;j>=1;j--)
    {
        if(a[(x-1)*m+j]=='X') break;
        win[(x-1)*m+j]=true;
    }
    for(int j=y;j<=m;j++)
    {
        if(a[(x-1)*m+j]=='X') break;
        win[(x-1)*m+j]=true;
    }
    for(int i=x,j=y;i>=1&&j>=1;i--,j--)
    {
        if(a[(i-1)*m+j]=='X') break;
        win[(i-1)*m+j]=true;
    }
    for(int i=x,j=y;i<=n&&j<=m;i++,j++)
    {
        if(a[(i-1)*m+j]=='X') break;
        win[(i-1)*m+j]=true;
    }
    for(int i=x,j=y;i>=1&&j<=m;i--,j++)
    {
        if(a[(i-1)*m+j]=='X') break;
        win[(i-1)*m+j]=true;
    } 
    for(int i=x,j=y;i<=n&&j>=1;i++,j--)
    {
        if(a[(i-1)*m+j]=='X') break;
        win[(i-1)*m+j]=true;
    }
}
bool check(int x,int y)
{
    if(x<1||x>n||y<1||y>m||vis[(x-1)*m+y]==true) return false;
    else return true;
}
bool work(int x,int y,int step)
{
    if(check(x,y)==true)
    {
        head++;
        q[head].x=x;
        q[head].y=y;
        q[head].step=step;
        vis[(x-1)*m+y]=true;
        if(win[(x-1)*m+y]==true)
        {
            return true;
        }
    }
    return false;
}
int bfs()
{
    head++;
    q[head].x=qx;
    q[head].y=qy;
    q[head].step=0;
    vis[(qx-1)*m+qy]=true;
    if(win[(qx-1)*m+qy]==true) return 0;
    while(head-tail+1>0)
    {
        int x=q[tail].x;
        int y=q[tail].y;
        int step=q[tail].step;
        tail++;
        if(work(x-1,y,step+1)==true) return step+1;
        if(work(x+1,y,step+1)==true) return step+1;
        if(work(x,y-1,step+1)==true) return step+1;
        if(work(x,y+1,step+1)==true) return step+1;
    }
    return -1;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[(i-1)*m+j];
        }
    }
    while(cin>>mx>>my>>qx>>qy)
    {
        if(qx==0&&qy==0&&mx==0&&my==0)
        {
            break;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                win[(i-1)*m+j]=false;
            }
        }
        init(mx,my);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                vis[(i-1)*m+j]=false;
                if(a[(i-1)*m+j]=='X') vis[(i-1)*m+j]=true;
            }
        }
        head=0,tail=1;
        int ans=bfs();
        if(ans==-1)
        {
            cout<<"Poor Harry"<<endl;
        }
        else
        {
            cout<<ans<<endl;
        }
    }
    return 0;
}

ヾ(￣▽￣)Bye~Bye~