Я пытаюсь решить задачу «Лабиринт CSES»:
Вам дана карта лабиринта, и ваша задача — найти путь от начала в конец. Вы можете ходить влево, вправо, вверх и вниз.
Ввод
Первая строка ввода содержит два целых числа n и m: высоту и ширину карту.
Тогда есть n строк по m символов, описывающих лабиринт. Каждый символ — это . (пол), # (стена), A (начало) или B (конец). На входе ровно один A и один B.
Вывод
Сначала выведите «YES», если путь есть, в противном случае — «НЕТ».
Если путь существует, выведите длину кратчайшего такого пути и его описание в виде строки, состоящей из символов L (слева), R (справа), U (вверх) и D (вниз). Вы можете вывести любое допустимое решение.
Ограничения
1 ≤ 𝑛, 𝑚 ≤ 1000
Пример< /h3>
Ввод:
5 8
########
#.A#...#
#.##.#B#
#......#
########
Вывод:
YES
9
LDDRRRRRU
Я реализовал алгоритм BFS. Он решает все тестовые случаи, кроме одного. В одном из тестовых случаев я получаю ошибку Превышен лимит времени (TLE).
Я пробовал различные подходы и смотрел множество решений на YouTube, но В этих решениях нет ничего особенного, что могло бы решить мою проблему, или я могу что-то упустить. Может ли кто-нибудь определить, где я ошибаюсь?
Мой код:
#include
#include
#include
using namespace std;
bool vis[1001][1001];
char path[1001][1001];
queue q;
vector moves = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1}};
vector final_path;
int n, m, sx, sy, ex, ey;
bool is_valid(int i, int j)
{
if (i < 0 || i >= n || j < 0 || j >= m)
{
return false;
}
if (vis[j])
return false;
return true;
}
bool bfs(int i, int j)
{
vis[j] = true;
q.push({i, j});
while (!q.empty())
{
pair f = q.front();
q.pop();
if (f.first == ex && f.second == ey)
{
int p = f.first;
int r = f.second;
while (p != sx or r != sy)
{
// cout
Подробнее здесь: https://stackoverflow.com/questions/784 ... th-problem
