c++MLE 10pts求调

syf_jrym @ 2023-12-03 10:29:42

#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
int c[1005][1005],cnt[1005][1005];
int dy[5]={0,-1,1,0};
int dx[5]={1,0,0,-1};
int x,y,xx,yy,n;
void bfs(){
    queue<PII>q;
    q.push({x,y});
    int x1,y1,xd,yd;
    while(!q.empty()){
        x1=q.front().first;
        y1=q.front().second;
        for(int i=0;i<4;++i){
            xd=x1+dx[i];
            yd=y1+dy[i];
            if(xd>0&&xd<=n&&yd>0&&yd<=n&&c[xd][yd]==0){
                if(cnt[xd][yd]>cnt[x1][y1]||cnt[xd][yd]==0){
                    q.push({xd,yd});
                    cnt[xd][yd]=cnt[x1][y1]+1;
                }
            }
        }
        q.pop();
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        string a;
        cin>>a;
        for(int j=0;j<a.size();++j){
            c[i][j+1]=a[j]-'0';
        }
    }
    cin>>x>>y>>xx>>yy;
    bfs();
    cout<<cnt[xx][yy];
} 

by xingyu671 @ 2023-12-06 11:46:59

我也是BFS,MLE了，0分

#include<bits/stdc++.h>
using namespace std;
char ma[1005][1005];
int dx[] = {0,1,0,-1,0},dy[] = {0,0,1,0,-1},n,sx,sy,fx,fy,ans = 0x3f3f3f3f; 
struct p
{
    int x;
    int y;
    int f;
    int b;
};
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) cin >> ma[i][j];
    cin >> sx >> sy >> fx >> fy;
    queue<p> q;
    q.push({sx,sy,0,0});
    while(!q.empty())
    {
        p t = q.front();
        q.pop();
        if(t.x < 1 || t.x > n || t.y < 1 || t.y > n || ma[t.x][t.y] == '1') continue;
        if(t.x == fx && t.y == fy) ans = min(ans,t.b);
        for(int i = 1;i <= 4;i++)
        {
            if(i == t.f) continue;
            q.push({t.x+dx[i],t.y+dy[i],(i+1)%4+1,t.b+1});
        }
    }
    cout << ans;
    return 0;
}

by lightme @ 2023-12-12 21:57:19

两个都mle了？

by lightme @ 2023-12-12 22:09:56

#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
int c[1005][1005],cnt[1005][1005];
int dy[5]={0,-1,1,0};
int dx[5]={1,0,0,-1};
int x,y,xx,yy,n;
void bfs(){
    //memset(cnt,-1,sizeof cnt);
    queue<PII>q;
    q.push({x,y});
    int x1,y1,xd,yd;
    while(!q.empty()){
        x1=q.front().first;
        y1=q.front().second;
        for(int i=0;i<4;++i){
            xd=x1+dx[i];
            yd=y1+dy[i];
            if(xd>0&&xd<=n&&yd>0&&yd<=n&&c[xd][yd]==0&&cnt[xd][yd]==0){
                //if(cnt[xd][yd]>cnt[x1][y1]||cnt[xd][yd]==0){
                    q.push({xd,yd});
                    cnt[xd][yd]=cnt[x1][y1]+1;
                //}
                //if(cnt[xx][yy]>0) return;
            }
        }
        q.pop();
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        string a;
        cin>>a;
        for(int j=0;j<a.size();++j){
            c[i][j+1]=a[j]-'0';
        }
    }
    cin>>x>>y>>xx>>yy;
    bfs();
    cout<<cnt[xx][yy];
} 

按照第一个bfs改的

by lightme @ 2023-12-12 22:13:19

if(cnt[xd][yd]>cnt[x1][y1]||cnt[xd][yd]==0)

这一句有点多余了因为后面的cnt下一个cnt都是大于前一个的按照bfs的特点来说，所以不需要做一步，估计你过的那个数据点就正好是样例，数据卡好的正好是最后一个数据所以无所谓。后面数据量大了就有问题了这里爆内存的估计是队列爆的，不是这个二维数组所以不用像下一个bfs一样做个结构体。小tip可以后面加个return这样稍微节约一点时间

by ARTI001 @ 2024-01-04 11:59:13

同样bfs，mle了:(

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstdlib>
using namespace std;

int n;
int map[1005][1005];
char a[1005][1005];
int x11,y11,x22,y22;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool vis[1005][1005];

struct node
{
    int x,y,count;
}fir;

queue <node>q;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            map[i][j]=a[i][j]-'0';
        }
    }
    cin>>x11>>y11>>x22>>y22;
    fir.x=x11;
    fir.y=y11;
    vis[x11][y11]=1;
    fir.count=0;
    q.push(fir);
    struct node top;
    while(q.empty()==0)
    {
        top=q.front();//cout<<top.x<<" "<<top.y<<endl;
        q.pop();
        if(top.x==x22&&top.y==y22)goto what;

        for(int i=0;i<4;i++)
        {
            struct node nxt;
            nxt.x=top.x+dx[i];
            nxt.y=top.y+dy[i];
            if(nxt.x<1||nxt.x>n||nxt.y<1||nxt.y>n)continue;
            if(map[nxt.x][nxt.y]==1)continue;
            if(vis[nxt.x][nxt.y]==1)continue;
            nxt.count=top.count+1;
            vis[top.x][top.y]=1;
            q.push(nxt);
        }
    }
    what:
        cout<<top.count;
    return 0;
}