关于队列和引用

butterbutterfly @ 2024-08-24 23:38:47

#include <iostream>
#include<cstring>
#include <cmath>
#include <utility>
#include <queue>
int n,m;
short start_x,start_y;
short ** map;
int max_step;
int incre_x[8]={-2,-1,1,2,2,1,-1,-2};
int incre_y[8]={-1,-2,-2,-1,1,2,2,1};

int main (void)
{
    std::cin>>n>>m>>start_x>>start_y;
    map=new short * [n];
    for(int i=0;i<n;i++)
    {
        map[i]=new short[m]();
        memset(map[i],-1,sizeof(short)*m);
    }
    std::queue<std::pair<short,short> > arr;    
    arr.push(std::make_pair(start_x-1,start_y-1));
    map[start_x-1][start_y-1]=0;    
    std::pair<short,short>& p=arr.front();  
    while(!arr.empty())
    {
        p=arr.front();

        int curr_level=map[p.first][p.second];      
        for( short j=0;j<8;j++)
        {
            if(p.first+incre_x[j]>=0&&p.first+incre_x[j]<n&&p.second+incre_y[j]>=0&&p.second+incre_y[j]<m&&map[p.first+incre_x[j]][p.second+incre_y[j]]==-1)
            {
                arr.push(std::make_pair(p.first+incre_x[j],p.second+incre_y[j]));
                map[p.first+incre_x[j]][p.second+incre_y[j]]=curr_level+1;
            }
        }
        arr.pop();  
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            std::cout<<map[i][j]<<' ';
        std::cout<<std::endl; 
    }
    return 0;
 } 

by Ben_coding @ 2024-08-29 16:11:52

AC代码如下，请自学：

#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,a[400][400],vis[400][400];
int dx[9]={0,1,2,2,1,-1,-2,-2,-1};
int dy[9]={0,2,1,-1,-2,-2,-1,1,2};
struct point{
    int x,y,step;
};
bool in(int x,int y){
    if (x<1||x>n) return false;
    if (y<1||y>m) return false;
    return true;
}
void bfs(int x,int y){
    queue <point> q;
    point p;
    p.x=x;p.y=y;p.step=0;
    q.push(p);
    while (q.size()){
        point np=q.front();
        int xx=np.x;
        int yy=np.y;
        int sstep=np.step;
        q.pop();
        for (int i=1;i<=8;i++){
            int nx=xx+dx[i];
            int ny=yy+dy[i];
            if (in(nx,ny)&&vis[nx][ny]==0){
                int nstep=sstep+1;
                point pp;
                pp.x=nx;
                pp.y=ny;
                pp.step=nstep;
                q.push(pp);
                vis[nx][ny]=1;
                a[nx][ny]=nstep;
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (a[i][j]==0) a[i][j]=-1;
        }
    }
    a[x][y]=0;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&x,&y);
    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;
}