3用例过不去,BFS

P1746 离开中山路

afreshmanofclanguage @ 2024-03-04 20:47:05

#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
using namespace std;
int x1, y11, x2, y2, n;
char arr[1005][1005];
int visit[1005][1005];
int xm[4] = { 0,1,0,-1 };
int ym[4] = { 1,0,-1,0 };
typedef pair<int, int> PII;
queue<PII> q;
int bfs(int x, int y)
{
    q.push({ x, y }); // 放入起点坐标
    while (q.size())
    {
        PII t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int a = t.first + xm[i];
            int b = t.second + ym[i];
            if (a < 1 || a > n || b < 1 || b > n || arr[a][b] == '1' || visit[a][b])
                continue;
            q.push({ a,b });
            visit[a][b] = visit[t.first][t.second] + 1;
            if (a == x2 && b == y2)
                return visit[a][b];
        }
    }
    return -1;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%s", arr[i]);
    cin >> x1 >> y11 >> x2 >> y2;
    cout << bfs(x1, y11);
    return 0;
}

by LYBT @ 2024-03-04 21:33:30

输入地图时,将 arr[i] 改为 arr[i]+1


|