BFS，9TLE+1AC

P1746 离开中山路

159号程序员 @ 2022-01-18 13:54:46

link，开O2后MLE link。

大概率是函数出现了问题，导致队列无限增加，出现MLE，不过找不出错/kk

代码结构大概率没有问题（这个结构我A了许多题了）

方向数组、边界条件等细节已仔细检查，没有任何问题。（甚至换成二楼题解的了）

仔细观察过许久，找不出来错误了，与二楼题解对拍第一个点就超时许多。

求大佬答疑解惑。

为了帖子版面工整，代码二楼

by 159号程序员 @ 2022-01-18 13:56:10

#include <iostream>
#include <queue>
using namespace std;

const int N = 1050;
int n, sx, sy, fx, fy, vis[N][N];
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
char a[N][N];

int bfs(int posx, int posy)
{
    queue <pair<pair<int, int>, int> > q;
    q.push(make_pair(make_pair(posx, posy), 0));
    while(!q.empty())
    {
        int x = q.front().first.first, y = q.front().first.second, round = q.front().second;
        q.pop();
        vis[x][y] = 1;
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || ny < 1 || nx > n || ny > n || vis[nx][ny] || a[nx][ny] == '1') continue;
            if(nx == fx && ny == fy) return round + 1;
            q.push(make_pair(make_pair(nx, ny), round + 1));
        }
    }
    return -1;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];
    cin >> sx >> sy >> fx >> fy;
    cout << bfs(sx, sy) << endl;
    return 0;
}

第 28 行的 return -1; 是为了函数严谨，会终止并返回错误值，但是问题肯定不在这里。

by fjy666 @ 2022-01-18 13:59:38

@159号程序员如果出队的时候标记，那么就可能会导致同一个东西多次入队，应该是这里错了

by 159号程序员 @ 2022-01-18 14:00:44

@fjy666 把 vis 标记移到循环里？

by Argon_Cube @ 2022-01-18 14:02:20

@159号程序员 Here.你是不是错了细节第二条？

by fjy666 @ 2022-01-18 14:03:23

@159号程序员就是在进队的时候 vis[x][y]=1 就行了qwq

by 159号程序员 @ 2022-01-18 14:03:47

@Epsilon_Cube 大概率是，我调一下看看

by 159号程序员 @ 2022-01-18 14:04:04

@fjy666 我试试看

by ud2_ @ 2022-01-18 14:04:17

 while(!q.empty())
 {
     int x = q.front().first.first, y = q.front().first.second, round = q.front().second;
     q.pop();
+    if (vis[x][y]) continue;
     vis[x][y] = 1;
     for(int i = 0; i < 4; i++)
     {
         int nx = x + dx[i], ny = y + dy[i];
-        if(nx < 1 || ny < 1 || nx > n || ny > n || vis[nx][ny] || a[nx][ny] == '1') continue;
+        if(nx < 1 || ny < 1 || nx > n || ny > n || a[nx][ny] == '1') continue;
         if(nx == fx && ny == fy) return round + 1;
         q.push(make_pair(make_pair(nx, ny), round + 1));
     }
 }

by 159号程序员 @ 2022-01-18 14:05:39

@ud2_ 理解

by 159号程序员 @ 2022-01-18 14:18:16

@fjy666 @ud2_ @Epsilon_Cube

感谢各位，AC了/qq