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好的,蟹蟹!