已过,但是很疑惑

P1443 马的遍历

ST_jz_xpj @ 2024-08-09 15:34:34

我用这个代码过了

#include<iostream>
#include<queue>
using namespace std;
int n,m,a,b,q[410][410];
bool f[410][410];
struct xy{
    int x,y,nt;
}p;
queue<xy> d;
int fx[8]={-2,-1,1,2,2,1,-1,-2};
int fy[8]={-1,-2,-2,-1,1,2,2,1};
void bfs(int x,int y,int num){
    if(!d.empty()){
        if(f[x][y]==0){
            q[x][y]=num;
            f[x][y]=1;
            for(int i=0;i<8;i++){
                if(x+fx[i]>0&&x+fx[i]<=n&&y+fy[i]>0&&y+fy[i]<=m&&f[x+fx[i]][y+fy[i]]==0){
                    p.x=x+fx[i];p.y=y+fy[i];p.nt=num+1;
                    d.push(p);
                }
            }
        }
        d.pop();
        bfs(d.front().x,d.front().y,d.front().nt);
    }
}
int main(){
    cin>>n>>m>>a>>b;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            q[i][j]=-1;f[i][j]=0;
        }
    }
    p.x=a;p.y=b;p.nt=0;
    d.push(p);
    bfs(a,b,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<q[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

但是用这个就是90分

#include<iostream>
#include<queue>
using namespace std;
int n,m,a,b,q[410][410];
bool f[410][410];
struct xy{
    int x,y,nt;
}p;
queue<xy> d;
int fx[8]={-2,-1,1,2,2,1,-1,-2};
int fy[8]={-1,-2,-2,-1,1,2,2,1};
void bfs(int x,int y,int num){
    if(!d.empty()){
        if(f[x][y]==0){
            q[x][y]=num;
            f[x][y]=1;
            for(int i=0;i<8;i++){
                if(x+fx[i]>0&&x+fx[i]<=n&&y+fy[i]>0&&y+fy[i]<=m&&f[x+fx[i]][y+fy[i]]==0){
                    p.x=x+fx[i];p.y=y+fy[i];p.nt=num+1;
                    d.push(p);
                }
            }
        }
        d.pop();
        bfs(d.front().x,d.front().y,d.front().nt);
    }
}
int main(){
    cin>>n>>m>>a>>b;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            q[i][j]=0;f[i][j]=0;
        }
    }
    p.x=a;p.y=b;p.nt=0;
    d.push(p);
    bfs(a,b,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i!=a&&j!=b&&q[i][j]==0)q[i][j]=-1;
            cout<<q[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

两个区别在一个先赋值-1,另一个是补漏没赋值且非起点的为-1 效果应该是相同的,但是一个AC,一个90分 why?


by Error_Eric @ 2024-08-09 15:40:07

@ST_jz_xpj 不是起点的正确判断方法是 !(i==a && j==b) 或者 (i!=a || j!=b)。不然一个不可到达点如果在起点同一行或者同一列就完蛋了。


by ymx2009 @ 2024-08-09 15:40:45

@ST_jz_xpj
if(i!=a&&j!=b&&q[i][j]==0)q[i][j]=-1;
应该是if(i!=a||j!=b&&q[i][j]==0)q[i][j]=-1;吧(猜测)


by ST_jz_xpj @ 2024-08-09 15:41:00

@Error_Eric奥!!!!! 蟹蟹dalao!! 懂了!!


by ST_jz_xpj @ 2024-08-09 15:41:17

@ Error_Eric


by ymx2009 @ 2024-08-09 15:41:59

if((i!=a||j!=b)&&q[i][j]==0)q[i][j]=-1
可能要打括号(刚刚忘了)


by ST_jz_xpj @ 2024-08-09 15:43:26

@ymx20090202好的,蟹蟹!


|