Алгоритм проверяет наличие пути к выходу из лабиринта, но только если строк в исходном файле меньше чем колонн
В первой строке исходного тхт файла указывается n и m, число колонн и строк соответственно, а дальше идет описание лабиринта, где x стена, o исходная позиция, w выход и - проход. n обозначает количество столбцов в лабиринте (считано с файла) m обозначает количество строк (тоже) w и k строка и столбец, который рассматривается в этом обороте цикла. Код выглядит так:
#include <iostream>
#include <queue>
#include <fstream>
#include <iomanip>
using namespace std;
struct pole { int w, k; };
int main() {
ifstream we("lab.txt");
int n, m, i, j;
pole p1, p2, p3;
we >> n >> m;
int Lab[n][m];
string s;
for (i = 0; i <= m; i++) {
we >> s;
for (j = 0; j<=n; j++) {
if (s[j] == 'x') Lab[i][j] = -1;
if (s[j] == 'o') {
Lab[i][j] = -2;
p1.w = i;
p1.k = j;
}
if (s[j] == 'w') {
Lab[i][j] = 0;
p3.w=i;p3.k=j;
}
else Lab[i][j] = 0;
}
}
we.close();
int w, k;
bool wyj = false;
queue<pole> Q;
Q.push(p1);
Lab[p1.w][p1.k] = 1;
while (!wyj && !Q.empty()) {
p2 = Q.front();
Q.pop();
w = p2.w;
k = p2.k;
if (w == p3.w && k == p3.k || w == p3.w && k == p3.k + 1 || w == p3.w && k == p3.k - 1 || w== p3.w + 1 && k == p3.k || w == p3.w - 1 && k == p3.k) {
wyj = true;
}
else {
if (w >= 0 && w <= m && k >= 0 && k <= n){
if (Lab[w-1][k]==0) {
Lab[w-1][k]=Lab[w][k]+1;
p2.w=w-1;
p2.k=k;
Q.push(p2);
}
if (Lab[w+1][k] == 0) {
Lab[w+1][k] = Lab[w][k]+1;
p2.w = w+1;
p2.k =k;
Q.push(p2);
}
if (Lab[w][k-1] == 0) {
Lab[w][k-1] = Lab[w][k] + 1;
p2.w = w;
p2.k = k-1;
Q.push(p2);
}
if (Lab[w][k+1]==0) {
Lab[w][k+1] = Lab[w][k] + 1;
p2.w = w;
p2.k = k + 1;
Q.push(p2);
}
}
}
}
if (wyj) cout << "TAK" << endl;
else cout << "NIE" << endl;
return 0;
}
И допустим для такого лабиринта:
9 8
---x-x---
xx-x-x---
---x-----
--xxxx---
--x--x---
-----x-o-
xxxx-----
------x-w
Выдает верный результат (проверено и с загароженным выходом). А если больше будет строк, а не колонн:
8 9
---x-x--
xx-x-x--
---x----
--xxxx--
--x--x--
-----x-o
xxxx----
------x-
-------w
Программа и с доступным, и с загороженным выходом будет утверждать, что выхода нет, хотя координаты вывести может. Выходит на то, что алгоритм не проходится по последней строке лабиринта, но почему не ясно.
P.S. Так же интересно почему если в строке if (w == p3.w && k == p3.k || w == p3.w && k == p3.k + 1 || w == p3.w && k == p3.k - 1 || w== p3.w + 1 && k == p3.k || w == p3.w - 1 && k == p3.k)
расставить скобки на подобии if ((w == p3.w && k == p3.k) || ...
результат работы программы меняется?
Ответы (1 шт):
В итоге комментатор оказался прав, действительно были перепутаны переменные по высоте и ширине в части по поиску выхода.