用vector没用queue爆MLE求改

butterbutterfly @ 2024-08-22 21:57:42

#include <iostream>
#include<cstring>
#include <cmath>
#include <vector>
#include <utility>
short n,m;
short start_x,start_y;
short ** map;
short max_step;

short incre_x[8]={-2,-1,1,2,2,1,-1,-2};
short incre_y[8]={-1,-2,-2,-1,1,2,2,1};

void draw(void)
{
    for(short i=0;i<n;i++)
    {
        for(short j=0;j<m;j++)
            std::cout<<map[i][j]<<' ';
        std::cout<<std::endl; 
    }
    std::cout<<std::endl; 
}

void bfs(short **ma,short step,std::vector<std::pair<short,short> >& arr)
{
    if(step>max_step)
        return ;
    int num=arr.size();
    std::vector<std::pair<short,short> > arr_next;
    //std::cout<<num<<std::endl;
    for(int i=0;i<num;i++)
    {
        ma[arr[i].first][arr[i].second]=step;
        for(short j=0;j<8;j++)
        {
            if(arr[i].first+incre_x[j]>=0&&arr[i].first+incre_x[j]<n&&arr[i].second+incre_y[j]>=0&&arr[i].second+incre_y[j]<m&&ma[arr[i].first+incre_x[j]][arr[i].second+incre_y[j]]==-1)
            {
                arr_next.push_back(std::make_pair(arr[i].first+incre_x[j],arr[i].second+incre_y[j]));
            }
        }
    }
    //draw();
    arr.clear();
    bfs(ma,step+1,arr_next);
}

int main (void)
{
    std::cin>>n>>m>>start_x>>start_y;

    map=new short * [n];

    for(short i=0;i<n;i++)
    {
        map[i]=new short[m]();
        memset(map[i],-1,sizeof(short)*m);
    }

    max_step=std::max(n,m);
    std::vector<std::pair<short,short> > arr;
    arr.push_back(std::make_pair(start_x-1,start_y-1));
    bfs(map,0,arr);
    //std::cout<<max_step<<std::endl;
    for(short i=0;i<n;i++)
    {
        for(short j=0;j<m;j++)
            std::cout<<map[i][j]<<' ';
        std::cout<<std::endl; 
    }

    return 0;
 } 

by QAQ_liu @ 2024-08-22 22:02:32

@butterbutterfly 这道题是深搜

#include<bits/stdc++.h>
using namespace std;
long long n,m,sx,sy,d[8][2]={{-2,-1},{-2,1},{-1,2},{-1,-2},{1,-2},{2,-1},{1,2},{2,1}},vis[1005][1005];
bool a[1005][1005];
void dfs(long long x,long long y,long long step){
    int nx,ny;
    for(int i=0;i<8;i++){
        nx=x+d[i][0];
        ny=y+d[i][1];
        if(nx>n||ny>m||nx<1||ny<1) continue;
        if(a[nx][ny]==1) continue;
        a[nx][ny]=1;
        vis[nx][ny]=min(vis[nx][ny],step);
        dfs(nx,ny,step+1);
        a[nx][ny]=0;

    }
}
int main(){
    cin>>n>>m>>sx>>sy;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            vis[i][j]=1e9;
        }
    }
    dfs(sx,sy,1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==sx&&j==sy) cout<<setw(5)<<0;
            else if(vis[i][j]==1e9) cout<<setw(5)<<-1;
            else cout<<setw(5)<<vis[i][j];
        }
        cout<<endl;
    }
    return 0;
}

by _zhang @ 2024-08-22 22:03:00

@butterbutterfly 我还是第一次看到能把bfs写成工程的代码

by QAQ_liu @ 2024-08-22 22:03:12

@butterbutterfly 说错了，是可以用

by _zhang @ 2024-08-22 22:03:57

可能是你没有出队操作？

by haimingbei @ 2024-08-22 22:04:40

@QAQ_liu 这不是广搜吗？（疑惑）

#include<bits/stdc++.h>
using namespace std;
    int n,m,x,y;
int a[410][410];//a[i][j]表示每个点最少需要几步 
bool b[410][410];//f[i][j]表示每个点是否走过 

int xp[9]={0,1,2,2,1,-1,-2,-2,-1};//x的偏移 
int yp[9]={0,-2,-1,1,2,2,1,-1,-2};//y的偏移

struct point{//结构体定义下标存进队列 
    int x,y;
};
queue <point> q;

void bfs(int x,int y){
    a[x][y]=0;
    b[x][y]=1;
    point f;
    f.x=x,f.y=y;
    q.push(f);
    int x1,y1;
    while(!q.empty()){
        x1=q.front().x;
        y1=q.front().y;
        q.pop();
        for(int i=1;i<=8;i++){
            int u=x1+xp[i],v=y1+yp[i];
            if(u>=1 && u<=n && v>=1 && v<=m && b[u][v]==0){
                a[u][v]=a[x1][y1]+1;
                b[u][v]=1;
                point t;
                t.x=u,t.y=v;
                q.push(t);
            }
        }
    }
}

int main(){
    cin>>n>>m>>x>>y;
    /*for(int i=1;i<=n;i++){
        for(j=1;j<=m;j++)a[i][j]=-1;
    }*/
    memset(a,-1,sizeof(a));//等价上面二重循环 
    bfs(x,y);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)printf("%5d",a[i][j]);
        printf("\n");
    }
    return 0;
}  

by _zhang @ 2024-08-22 22:04:49

话说数组和queue那么好用用vector干嘛

by haimingbei @ 2024-08-22 22:04:55

@butterbutterfly

by haimingbei @ 2024-08-22 22:05:26

@QAQ_liu 而且是广搜板子

by QAQ_liu @ 2024-08-22 22:05:42

@haimingbei 我不是说了吗，是可以用

by haimingbei @ 2024-08-22 22:06:31

@QAQ_liu 没看到