50求调

宋欣龙 @ 2024-10-23 22:10:27

#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=410;
int dx[8]={-1,-2,-2,-1,1,2,2,1};
int dy[8]={2,1,-1,-2,2,1,-1,-2};
int n,m,x,y;
bool vis[N][N];
int ans[N][N];
struct edge{
    int x,y;
};
queue<edge>q;
int bfs(int a,int b){
    edge e;e.x=a;e.y=b;q.push(e);
    while(!q.empty()){
        edge st=q.front();q.pop();
        for(int i=0;i<8;i++){
            edge nx;nx.x=st.x+dx[i];nx.y=st.y+dy[i];
            if(nx.x>=1&&nx.x<=n&&nx.y>=1&&nx.y<=m&&vis[nx.x][nx.y]==0){
                vis[nx.x][nx.y]=1;
                ans[nx.x][nx.y]=ans[st.x][st.y]+1;
                q.push(nx);
            }
        }
    }
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>x>>y;
    memset(ans,-1,sizeof(ans));
    ans[x][y]=0;vis[x][y]=1;
    bfs(x,y);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%-5d",ans[i][j]);
        }cout<<endl;
    }
    return 0;
}

by 宋欣龙 @ 2024-10-23 22:13:03

为什么开了O2后RE，没开O2的话50分？

by tengyuxuan @ 2024-11-09 22:01:55

#include <bits/stdc++.h>
using namespace std;

struct node{
    int x,y,step;
};
queue<node> q;
int n,m,sx,sy;
int mp[410][410];
int fx[]={0,-2,-2,-1,1,2,2,1,-1};
int fy[]={0,-1,1,2,2,1,-1,-2,-2};
void bfs(){
    node st;
    st.x=sx;
    st.y=sy;
    st.step=0; 
    mp[sx][sy]=0;
    q.push(st);
    while(!q.empty()){
        node bf=q.front();
        int bx,by;
        bx=bf.x;
        by=bf.y;
        for(int i=1;i<=8;i++){
            int dx,dy;
            dx=bx+fx[i];
            dy=by+fy[i];
            if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&mp[dx][dy]==-1){
                node newone;
                newone.x=dx;
                newone.y=dy;
                newone.step=bf.step+1;
                mp[dx][dy]=bf.step+1;
                q.push(newone);
            } 
        }
        q.pop();
    }
}
int main(){
    cin>>n>>m>>sx>>sy;
    memset(mp,-1,sizeof(mp));
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<setw(5)<<mp[i][j];
        }
        cout<<endl;
    }
    return 0;
}