Постройте граф, в котором вершинами являются кортежи (Sx, Sy, Bx, By), описывающие текущее положение игрока Sokoban, (Sx, Sy) и поле (Bx, By). Запишите минимальную стоимость, известную для достижения каждой позиции, и выполните BFS, используя очередь приоритетов, чтобы найти кратчайший путь к позиции, где ящик достигает целевой ячейки. это код, сгенерированный …
Формат ввода
Первая строка состоит из двух целых чисел r и c (оба ≤ 20), представляющих количество строк и столбцов лабиринта, соответственно
После этого идут r строк, каждая из которых содержит c символов. Каждый персонаж описывает одну ячейку лабиринта. Ячейка, полная камня, обозначена символом «#», а пустая ячейка представлена знаком «.». Ваша начальная позиция обозначается буквой «S», начальная позиция поля — буквой «B», а ячейка назначения — буквой «T».
Выходной формат
Если невозможно перенести коробку в целевую ячейку, выведите -1.
В противном случае выведите два целых числа P и W в одной строке, где P — количество нажатий, а W — количество прогулок в оптимальном решении.
HERE IS THE CODE.... my problem is when input is:
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
output appears as -1. whereas it should hav been 6 22
подскажите пожалуйста в чем ошибка в коде ..
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
const int MAX = 20 + 5;
char map[MAX][MAX];
int visPerson[MAX][MAX];
int visBox[MAX][MAX];
int R, C;
int dir[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
char pushes[4] = {'E', 'W', 'S', 'N'};
char walks[4] = {'e', 'w', 's', 'n'};
string path;
struct NODE
{
int br, bc;
int pr, pc;
string ans;
};
int InMap(int r, int c)
{
return (r >= 1 && r <= R && c >= 1 && c <= C);
}
int Bfs2(int sr, int sc, int er, int ec, int br, int bc, string &ans)
{
queue<NODE> q;
NODE node, tmpNode;
node.pr = sr; node.pc = sc; node.ans = "";
q.push(node);
visPerson[br][bc] = 1;
while (!q.empty())
{
node = q.front();
q.pop();
if (node.pr==er && node.pc==ec) { ans = node.ans; return 1; }
if (visPerson[node.pr][node.pc]) continue;
visPerson[node.pr][node.pc] = 1;
for (int i=0; i<4; i++)
{
int nr = node.pr + dir[i][0]; int nc = node.pc + dir[i][1];
if (InMap(nr, nc) && !visPerson[nr][nc] && map[nr][nc] !='#')
{
tmpNode.pr = nr; tmpNode.pc = nc; tmpNode.ans = node.ans+ walks[i];
q.push(tmpNode);
}
}
}
return 0;
}
int Bfs1(int sr, int sc, int br, int bc)
{
queue<NODE> q;
NODE node, tmpNode;
node.pr = sr; node.pc = sc; node.br = br; node.bc = bc; node.ans ="";
q.push(node);
while (!q.empty())
{
node = q.front();
q.pop();
if (visBox[node.br][node.bc]) continue;
visBox[node.br][node.bc] = 1;
if (map[node.br][node.bc] == 'T')
{
path = node.ans; return 1;
}
for (int i=0; i<4; i++)
{
int nextr = node.br + dir[i][0];
int nextc = node.bc + dir[i][1];
int backR = node.br - dir[i][0];
int backC = node.bc - dir[i][1];
string ans = "";
if (InMap(backR, backC) && InMap(nextr, nextc) && map[nextr][nextc] != '#'&& map[backR][backC] != '#' && !visBox[nextr][nextc])
{
if (Bfs2(node.pr, node.pc, backR, backC, node.br, node.bc, ans))
{
tmpNode.pr = node.br; tmpNode.pc = node.bc;
tmpNode.br = nextr; tmpNode.bc = nextc;
tmpNode.ans = node.ans + ans + pushes[i];
q.push(tmpNode);
}
}
}
}
return 0;
}
int main()
{ int push=0,walk=0,len;
string str;
int i=1;
int r=0;
int sr, sc;
int br, bc;
int cases = 1;
cin>>R>>C;
for (int r=1; r<=R; r++)
{
for (int c=1; c<=C; c++)
{
cin >> map[r][c];
if (map[r][c] == 'S'){ sr = r; sc = c; }
else if (map[r][c] == 'B') { br = r; bc = c; }
}
}
path = "";
r= Bfs1(sr, sc, br, bc);
if (r)
{
str=path;
len= str.size();
int a1= count(str.begin(),str.end(),'s');
int a2= count(str.begin(),str.end(),'w');
int a3= count(str.begin(),str.end(),'e');
int a4= count(str.begin(),str.end(),'n');
cout<< len - (a1+a2+a3+a4) << " " <<(a1+a2+a3+a4) << "\n";
}
else
cout<< "-1"<<"\n";
return 0;
}
Задача ещё не решена.
Других решений пока нет …