MLE求助

P1746 离开中山路

a_bad_seed @ 2023-01-13 15:19:24

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
struct node
{
    int x, y;
    int step;
} a, b;
int n;
char c[1010][1010];
int maze[1010][1010];
bool vis[1010][1010];
int dir[4][4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int x_1, y_1, x_2, y_2;
queue<node> q;

bool in(int x, int y)
{
    return 0 <= x && x < n && 0 <= y && y < n;
}
int main()
{
    //    freopen(".in","r",stdin);
    //    freopen(".out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> c[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            maze[i][j] = c[i][j] - '0';
        }
    }
    cin >> x_1 >> y_1 >> x_2 >> y_2;
    x_1--, y_1--, x_2--, y_2--;
    if (x_1 == x_2 && y_1 == y_2)
    {
        cout << 0;
        return 0;
    }
    q.push((node){x_1, y_1, 0});
    vis[x_1][y_1] = 1;
    while (!q.empty())
    {
        a = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int dx = a.x + dir[i][0];
            int dy = a.y + dir[i][1];
            if (!vis[dx][dy] && !maze[dx][dy] && in(dx, dy))
            {
                b.x = dx;
                b.y = dy;
                b.step = a.step + 1;
                if (dx == x_2 && dy == y_2)
                {
                    cout << b.step;
                    return 0;
                }
                q.push(b);
            }
        }
    }
    //    fclose(stdin);
    //    fclose(stdout);
    return 0;
}

by Fractured_Angel @ 2023-01-13 15:39:20

目测bfs里根本没标记vis?


by a_bad_seed @ 2023-01-13 15:39:56

啊对对对


by a_bad_seed @ 2023-01-13 15:40:06

解决了


|