Использование BFS в простом решателе Rush Hour — почему мой код не решает проблемы?
ОБНОВЛЕНИЕ — Основная проблема была решена ответчиком ниже (у меня было ‘=’, где у меня должно было быть ‘==’), но теперь я получаю неправильный вывод. Я думал, что приведу несколько примеров ввода / вывода, как это было предложено, так что, возможно, кто-то там может определить, где я иду не так.
Скажем, я ввожу ввод:
......
......
xx....
......
......
......
Это должно привести к выводу:
4
x r
x r
x r
x r
чтобы обозначить х, попал в самое правильное место 3-го ряда за 4 хода, и х нужно было сдвигать вправо каждый ход.
Вместо этого я получаю вывод:
3
x r
x l
x r
В приведенном ниже коде программа принимает блок символов 6х6 для представления игрового поля. (точки — это пустые места, символы представляют автомобили.) Работа, проделанная в классе доски и основной функции, правильная, как я проверил у своего профессора. Тем не менее, я пытаюсь исправить свой вывод. Я знаю, что моя логика, используемая в функции решения, не является лучшим подходом для этого, но я должен попытаться заставить ее работать, чтобы я мог получить очки назад, не копируя решение профессора.
#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <list>
using namespace std;
class board
{
public:
board() {count = 0;}
bool isSolved()
{
return currState[17] = 'x';
}
string currState;
string moveList;
int count;
};
bool operator < (const board& board1, const board& board2)
{
return board1.currState < board2.currState;
}
void solve (const board& curr, int i, list<board>& toTest, const set<board>& testedSet, bool vert)
{
board newMove(curr);
if (vert == false)
{
if (i % 6 == 0 && curr.currState[i] != '.')
{
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i+2] == '.')
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
newMove.currState[i+2] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i] == curr.currState[i+2] && curr.currState[i+3] == '.')
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
newMove.currState[i+3] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
}
else if ((i + 1) % 6 == 0 && curr.currState[i] != '.')
{
if (curr.currState[i] == curr.currState[i-1] && curr.currState[i-2] == '.')
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
newMove.currState[i-2] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
if (curr.currState[i] == curr.currState[i-1] && curr.currState[i] == curr.currState[i-2] && curr.currState[i-3] == '.')
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
newMove.currState[i-3] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
}
else
{
if (i % 2 != 0 && i % 3 != 0 && curr.currState[i] != '.')
{
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i-1] == '.' && curr.currState[i+2] != curr.currState[i])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
newMove.currState[i-1] = newMove.currState[i];
newMove.currState[i+1] = '.';
newMove.count++;
}
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i+2] == '.' && curr.currState[i-1] != curr.currState[i])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
newMove.currState[i+2] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i] == curr.currState[i+2] && curr.currState[i-1] == '.' && curr.currState[i+3] != curr.currState[i])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
newMove.currState[i-1] = newMove.currState[i];
newMove.currState[i+2] = '.';
newMove.count++;
}
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i] == curr.currState[i+2] && curr.currState[i+3] == '.' && curr.currState[i-1] != curr.currState[i])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
newMove.currState[i+3] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
}
if (i % 2 == 0 && (i + 2) % 6 != 0 && curr.currState[i] != '.')
{
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i-1] == '.' && curr.currState[i+2] != curr.currState[i])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
newMove.currState[i-1] = newMove.currState[i];
newMove.currState[i+1] = '.';
newMove.count++;
}
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i+2] == '.' && curr.currState[i-1] != curr.currState[i])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
newMove.currState[i+2] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i] == curr.currState[i+2] && curr.currState[i+3] == '.' && curr.currState[i-1] != curr.currState[i])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
newMove.currState[i+3] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
}
if (i % 3 == 0 && curr.currState[i] != '.')
{
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i-1] == '.' && curr.currState[i+2] != curr.currState[i])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "l" + "\n";
newMove.currState[i-1] = newMove.currState[i];
newMove.currState[i+1] = '.';
newMove.count++;
}
if (curr.currState[i] == curr.currState[i+1] && curr.currState[i+2] == '.' && curr.currState[i-1] != curr.currState[i])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "r" + "\n";
newMove.currState[i+2] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
}
}
}
if (vert == true)
{
if (i < 17)
{
if (curr.currState[i] == curr.currState[i+6] && curr.currState[i] == curr.currState[i+12] && curr.currState[i+18] == '.')
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "d" + "\n";
newMove.currState[i+18] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
if (curr.currState[i] == curr.currState[i+6] && curr.currState[i+12] == '.')
{
if (i < 6 || curr.currState[i] != curr.currState[i-6])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "d" + "\n";
newMove.currState[i+12] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
}
}
if (i > 17)
{
if (curr.currState[i] == curr.currState[i-6] && curr.currState[i] == curr.currState[i-12] && curr.currState[i-18] == '.')
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "u" + "\n";
newMove.currState[i-18] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
if (curr.currState[i] == curr.currState[i-6] && curr.currState[i-12] == '.')
{
if (i > 29 || curr.currState[i] != curr.currState[i+6])
{
newMove.moveList = newMove.moveList + newMove.currState[i] + " " + "u" + "\n";
newMove.currState[i-12] = newMove.currState[i];
newMove.currState[i] = '.';
newMove.count++;
}
}
}}
if (testedSet.find(newMove) == testedSet.end())
toTest.push_back(newMove);
}
int main()
{
list<board> toBeTested;
string input;
board current;
set<board> tested;
bool vertical = false;
for (int i = 0; i < 6; i++)
{
getline(cin, input);
current.currState += input;
}
toBeTested.push_back(current);
while (toBeTested.size() > 0 && current.isSolved() == false)
{
current = toBeTested.front();
toBeTested.pop_front();
if (current.isSolved() == false && tested.find(current) == tested.end())
{
tested.insert(current);
for (int i = 0; i < 36; i++)
{
solve(current, i, toBeTested, tested, vertical);
vertical = true;
solve(current, i, toBeTested, tested, vertical);
vertical = false;
}
}
}
if (current.isSolved() == false)
cout << current.count << endl << current.moveList;
else
cout << -1 << endl;
return 0;
}
Решение
Трудно понять, что вы пытаетесь сделать здесь, потому что многие значения жестко запрограммированы и в программе не используется много абстракций.
Я предполагаю, что вы пытаетесь сделать что-то вроде http://www.theiling.de/projects/rushhour.html где входная плата похожа на:
aaobcc ..ob .. XXO ... deeffp d..k.p hh.k.p
Если вы сделаете исправление board::isSolved() из моего комментария:
bool isSolved()
{
return currState[17] == 'x';
}
Вы по крайней мере получите что-то кроме -1:
10 б д с л час ты ты ты ф р к тебе ч л час
Однако это не является решением проблемы ввода.
Не похоже, что вы правильно вычисляете следующие состояния. Должен быть цикл для итерации каждого элемента транспортного средства после его перемещения.
Обязательно попробуйте абстрагировать больше деталей. Например, возможно, вы можете добавить методы board для (1) вычисления списка допустимых ходов и (2) применения одного хода, возврата нового board, Кроме того, если вы не научились использовать отладчик, такой как gdbсейчас самое время начать учиться. Увидеть Как использовать отладчик MinGW GDB для отладки программы C ++ в Windows?
Другие решения
Других решений пока нет …