c++ - 在一个简单的 Rush Hour 求解器中使用 BFS - 为什么我的代码不能求解电路板？

Question

更新 - 主要问题由下面的回复者解决（我有一个'='，我应该有一个'=='），但现在我得到了错误的输出。我想我会按照建议提供一些输入/输出示例，所以也许有人可以发现我哪里出错了。

假设我输入输入：

......

......

xx....

......

......

......

这应该产生输出：

4

x r

x r

x r

x r

表示 x 在 4 步中到达了第 3 行的最右边的位置，并且 x 必须每步向右移动。

相反，我得到了输出：

3

x r

x l

x r

在下面的代码中，程序接受一个 6x6 的字符块来表示游戏板。（句号是空格，字符代表汽车。）在板类和主要功能中完成的工作是正确的，因为我已经与我的教授核实过。但是，我正在尝试纠正我的输出。我知道我在求解函数中使用的逻辑不是最好的方法，但我必须尝试让它发挥作用，这样我就可以在不复制教授的解决方案的情况下拿回分数。

#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;
}

score 0 · Accepted Answer

很难弄清楚您在这里尝试做什么，因为许多值都是硬编码的，并且程序中没有使用很多抽象。

我猜你正在尝试做类似http://www.theiling.de/projects/rushhour.html的事情，其中输入是一个板，如：

aaobcc
..ob..
xx...
deeffp
d..kp
hh.kp

如果您对board::isSolved()我的评论进行更正：

bool isSolved()
{
    return currState[17] == 'x';
}

你至少会得到-1以外的东西：

10
BD
分类
小时
普
普
普
FR
苦
升
小时

但是，这不是输入问题的解决方案。

看起来您没有正确计算下一个状态。移动车辆后，应该有一个循环遍历车辆的每一部分。

绝对尝试抽象更多细节。例如，也许您可以将方法添加到board(1) 计算有效移动列表和 (2) 应用单个移动，返回一个新的board. 此外，如果您还没有学会如何使用诸如之类的调试器，那么gdb现在将是开始学习的绝佳时机。请参阅如何使用 MinGW gdb 调试器在 Windows 中调试 C++ 程序？

c++ - 在一个简单的 Rush Hour 求解器中使用 BFS - 为什么我的代码不能求解电路板？

1 回答 1

Related

Reference