水题玄学MLE求助。。。

P1746 离开中山路

xiaolou @ 2018-10-04 13:14:35

https://www.luogu.org/record/show?rid=11467018//23333222

#include <bits/stdc++.h>

using namespace std;
char m[1005][1005];
bool vis[1005][1005];
struct Node
{
    int x,y;
    int step;
};
int movex[4]={0,0,1,-1};
int movey[4]={1,-1,0,0};
queue <Node> q; 
int n;
int bfs(int x,int y,int endx,int endy)
{
    Node now;
    now.x=x;
    now.y=y;
    now.step=0;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            Node next;
            next.x=now.x+movex[i];
            next.y=now.y+movey[i];
            if(next.x>=1&&next.y>=1||next.x<=n&&next.y<=n&&vis[next.x][next.y]==false&&m[next.x][next.y]=='0')
            {
                if(next.x==endx&&next.y==endy)
                    return next.step;
                vis[next.x][next.y]=true;
                next.step=now.step+1;
                q.push(next);
            } 
        }
    }
}

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin >> m[i][j];
    int x,y;
    cin >> x >> y;
    int endx,endy;
    cin >> endx >> endy;
    cout << bfs(x,y,endx,endy);
    return 0; 
}

by NaCly_Fish @ 2018-10-04 13:35:03

把bool换成bitset试试


by NaCly_Fish @ 2018-10-04 13:35:42

@NaCly_Fish 内存可以少\frac78


by xiaolou @ 2018-10-04 13:36:38

@NaCly_Fish 怎么改。。。我不会。。。


by NaCly_Fish @ 2018-10-04 13:38:41

@xiaolou 搞一个存bitset的数组;只需要

bitset<1003> b;

就可以创建一个名为b的bitset,可以下标查询,每一项存的都是一个bit,所以可以当作bool使


by NaCly_Fish @ 2018-10-04 13:39:01

@NaCly_Fish 那个1003代表的是bitset的大小


by NaCly_Fish @ 2018-10-04 13:41:06

啊对了,没看见,把

    、if(next.x>=1&&next.y>=1||next.x<=n&&next.y<=n&&vis[next.x][next.y]==false&&m[next.x][next.y]=='0') 中的||改成&&

by xiaolou @ 2018-10-04 13:41:11

那要是二位的呢。。。 @NaCly_Fish


by xiaolou @ 2018-10-04 13:42:56

二维。。。


by NaCly_Fish @ 2018-10-04 13:44:29

@xiaolou 你说哪个二位的。。。我太弱看不懂您什么意思


by eros1on @ 2018-10-04 13:45:37

@xiaolou 小LouYu,大智慧!


| 下一页