Kle1N @ 2023-03-17 14:03:07
事情是这样的
我在写P1746这道题的时候,原本是用一个cnt变量来记录步数的,代码如下:
#include <bits/stdc++.h>
#define y1 yy
using namespace std;
int mx[4]={-1,1,0,0},my[4]={0,0,-1,1};
int n,x1,y1,x2,y2,road[1145][1145],qx[114514],qy[114514],headx,tailx,heady,taily,cnt;
bool v[1145][1145];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int ii=1;ii<=n;ii++){
char c;
cin>>c;
road[i][ii]=c-'0';
}
cin>>x1>>y1>>x2>>y2;
qx[++tailx]=x1;qy[++taily]=y1;
v[x1][y1]=1;
while(headx < tailx && heady < taily){
int x=qx[++headx];
int y=qy[++heady];
if(x == x2 && y == y2){
cout<<cnt<<endl;
return 0;
}
for(int i=0;i<4;i++){
if(!v[x+mx[i]][y+my[i]] && !road[x+mx[i]][y+my[i]] && x+mx[i] > 0 && x+mx[i] <= n && y+my[i] > 0 && y+my[i] <= n){
v[x+mx[i]][y+my[i]]=1;
qx[++tailx]=x+mx[i];qy[++taily]=y+my[i];
}
}
cnt++;
}
return 0;
}
结果全WA了
于是请教同机房大佬,加了一个记录步数的队列,代码如下:
#include <bits/stdc++.h>
#define y1 yy
using namespace std;
int mx[4]={-1,1,0,0},my[4]={0,0,-1,1};
int n,x1,y1,x2,y2,road[1145][1145],qx[114514],qy[114514],qq[114514],headx,tailx,heady,taily,headq,tailq,cnt;
bool v[1145][1145];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int ii=1;ii<=n;ii++){
char c;
cin>>c;
road[i][ii]=c-'0';
}
cin>>x1>>y1>>x2>>y2;
qx[++tailx]=x1;qy[++taily]=y1;qq[++tailq]=0;
v[x1][y1]=1;
while(headx < tailx && heady < taily && headq < tailq){
int x=qx[++headx];
int y=qy[++heady];
int q=qq[++headq];
if(x == x2 && y == y2){
cout<<q<<endl;
return 0;
}
for(int i=0;i<4;i++){
if(!v[x+mx[i]][y+my[i]] && !road[x+mx[i]][y+my[i]] && x+mx[i] > 0 && x+mx[i] <= n && y+my[i] > 0 && y+my[i] <= n){
v[x+mx[i]][y+my[i]]=1;
qx[++tailx]=x+mx[i];qy[++taily]=y+my[i];qq[++tailq]=q+1;
}
}
cnt++;
}
return 0;
}
然后70pts
代码看起来没问题,于是我就把cnt删掉了,代码如下:
#include <bits/stdc++.h>
#define y1 yy
using namespace std;
int mx[4]={-1,1,0,0},my[4]={0,0,-1,1};
int n,x1,y1,x2,y2,road[1145][1145],qx[114514],qy[114514],qq[114514],headx,tailx,heady,taily,headq,tailq;
bool v[1145][1145];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int ii=1;ii<=n;ii++){
char c;
cin>>c;
road[i][ii]=c-'0';
}
cin>>x1>>y1>>x2>>y2;
qx[++tailx]=x1;qy[++taily]=y1;qq[++tailq]=0;
v[x1][y1]=1;
while(headx < tailx && heady < taily && headq < tailq){
int x=qx[++headx];
int y=qy[++heady];
int q=qq[++headq];
if(x == x2 && y == y2){
cout<<q<<endl;
return 0;
}
for(int i=0;i<4;i++){
if(!v[x+mx[i]][y+my[i]] && !road[x+mx[i]][y+my[i]] && x+mx[i] > 0 && x+mx[i] <= n && y+my[i] > 0 && y+my[i] <= n){
v[x+mx[i]][y+my[i]]=1;
qx[++tailx]=x+mx[i];qy[++taily]=y+my[i];qq[++tailq]=q+1;
}
}
}
return 0;
}
然后玄学的事情就发生了,我提交上去只有30pts!
求大佬帮帮本蒟蒻吧(悲)
真的是给我气笑了
by Liquefyx @ 2023-03-17 14:37:23
应该是数组开小了吧?
by Liquefyx @ 2023-03-17 14:43:38
把qx,qy,qq这三个数组都开到1000005试试
by Kle1N @ 2023-03-21 17:39:36
@CE_Automata 真的耶,我把数组开到114514191就AC了!大佬orz
但还是和cnt有啥关系
by Liquefyx @ 2023-03-21 21:40:04
@houwz351 cnt是指前面有过多少个点,不是指的移动了多少步哦qwq,只用cnt肯定是WA的
by Liquefyx @ 2023-03-21 21:40:38
@houwz351 应该是数组越界搞的鬼