没有TLE,但是MLE,求指点

P1443 马的遍历

littlejohn @ 2024-08-10 22:26:53

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int table[401][401],n,m,x,y,v,xna,yna;
int stepx[]={1, 2 ,2,1,-1,-2,-2,-1},
    stepy[]={-2,-1,1,2,2 ,1 ,-1,-2};
struct Pos{
    int x,y,v;
};
queue<Pos> q;
Pos t,pos;
int main(){
    memset(table,-1,sizeof(table));
    cin>>n>>m>>x>>y;
    table[x][y]=0;
    pos.x = x;
    pos.y = y;
    pos.v = 0; 
    q.push(pos);
    while(q.empty()==0){
        pos = q.front();
        q.pop();
        if(table[pos.x][pos.y]==-1)table[pos.x][pos.y] = pos.v;
        for(int i=0;i<=7;i++){
            xna = pos.x+stepx[i];
            yna = pos.y+stepy[i];
            if((1<=xna && xna<=n)&&(yna>=1 &&yna<=m)){
                if(table[xna][yna]==-1){
                    t.x = xna;
                    t.y = yna;
                    t.v = pos.v + 1;
                    q.push(t);
                }
            }

        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<table[i][j]<<' ';
        }   
        cout<<endl;
    }
    return 0;
}

最后就这样了 问题在哪里 求指导


by meifan666 @ 2024-08-10 22:34:21

@littlejohn 入队列就要判断行不行,否则队列空间太大了

(顺带一提,这不是我们班长嘛!好久不见)


by meifan666 @ 2024-08-10 22:34:48

@littlejohn 参考一下

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

int n, m;
bool b[401][401];
int ans[401][401];
int opt[8][2] = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};

struct place {
    int x, y;
};
queue<place> q;

int main() {
    cin >> n >> m;
    int mx, my;
    cin >> mx >> my;
    place a;
    a.x = mx;
    a.y = my;
    q.push(a);
    b[mx][my] = 1;
    while (!q.empty()) {
        place now = q.front();
        q.pop();
        for (int i = 0; i <= 7; i++) {
            int x = now.x, y = now.y;
            int u = x + opt[i][0];
            int v = y + opt[i][1];
            if (u >= 1 && u <= n && v >= 1 && v <= m && !b[u][v]) {
                ans[u][v] = ans[x][y] + 1;
                b[u][v] = 1;
                q.push({u, v});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if(i!=mx||j!=my){
                if(ans[i][j]==0)ans[i][j]=-1;
            }
            if(j!=1)printf("%5d",ans[i][j]);
            else printf("%d", ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}

by meifan666 @ 2024-08-10 22:44:19

@littlejohn 好像不是这个问题

你 step 的两个数组开个10试试


by littlejohn @ 2024-08-11 18:43:30

@meifan666 可是我这里有判断啊

if(table[xna][yna]==-1)

应该也许不是这个问题


by littlejohn @ 2024-08-11 18:45:14

@meifan666 另外,也不是那里的问题QAQ(指数组)


by meifan666 @ 2024-08-11 19:28:55

@littlejohn 亲测AC改法:

table[x][y]=0;

删掉

if(table[pos.x][pos.y]==-1)table[pos.x][pos.y] = pos.v;

下面加上

else continue;

by littlejohn @ 2024-08-11 19:39:49

@meifan666 我试了好像没用 是这样吗?```cpp

include<iostream>

include<queue>

include<cstring>

using namespace std; int table[401][401],n,m,x,y,v,xna,yna; int stepx[]={1, 2 ,2,1,-1,-2,-2,-1}, stepy[]={-2,-1,1,2,2 ,1 ,-1,-2}; struct Pos{ int x,y,v; }; queue<Pos> q; Pos t,pos; int main(){ memset(table,-1,sizeof(table)); cin>>n>>m>>x>>y; pos.x = x; pos.y = y; pos.v = 0; q.push(pos); while(q.empty()==0){ pos = q.front(); q.pop(); if(table[pos.x][pos.y]==-1)table[pos.x][pos.y] = pos.v; for(int i=0;i<=7;i++){ xna = pos.x+stepx[i]; yna = pos.y+stepy[i]; if((1<=xna && xna<=n)&&(yna>=1 &&yna<=m)){ if(table[xna][yna]==-1){ t.x = xna; t.y = yna; t.v = pos.v + 1; q.push(t); } }else continue;

    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cout<<table[i][j]<<' ';
    }   
    cout<<endl;
}
return 0;

}


by littlejohn @ 2024-08-11 19:40:43

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int table[401][401],n,m,x,y,v,xna,yna;
int stepx[]={1, 2 ,2,1,-1,-2,-2,-1},
    stepy[]={-2,-1,1,2,2 ,1 ,-1,-2};
struct Pos{
    int x,y,v;
};
queue<Pos> q;
Pos t,pos;
int main(){
    memset(table,-1,sizeof(table));
    cin>>n>>m>>x>>y;
    pos.x = x;
    pos.y = y;
    pos.v = 0; 
    q.push(pos);
    while(q.empty()==0){
        pos = q.front();
        q.pop();
        if(table[pos.x][pos.y]==-1)table[pos.x][pos.y] = pos.v;
        for(int i=0;i<=7;i++){
            xna = pos.x+stepx[i];
            yna = pos.y+stepy[i];
            if((1<=xna && xna<=n)&&(yna>=1 &&yna<=m)){
                if(table[xna][yna]==-1){
                    t.x = xna;
                    t.y = yna;
                    t.v = pos.v + 1;
                    q.push(t);
                }
            }else continue;

        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<table[i][j]<<' ';
        }   
        cout<<endl;
    }
    return 0;
}

by meifan666 @ 2024-08-11 19:41:20

@littlejohn if下面直接加(代码不到万不得已就不发了


by meifan666 @ 2024-08-11 19:41:50

@littlejohn 直接加else那句


| 下一页