什么玄学东西???

P1746 离开中山路

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 应该是数组越界搞的鬼


|