c++ - 在简单的高峰时段求解器中使用 BFS - 为什么我的代码无法求解电路板？

Question

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

假设我输入:

......

......

xx....

......

......

......

这应该产生输出:

4

x r

x r

x r

x r

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

相反，我得到了输出:

3

x r

x l

x r

在下面的代码中，程序接受一个 6x6 的字符 block 来表示游戏板。 (句点是空格，字符代表汽车。)在 board 类和 main 函数中完成的工作是正确的，因为我已经与我的教授验证过。但是，我正在尝试更正我的输出。我知道我在求解函数中使用的逻辑不是解决此问题的最佳方法，但我必须尝试让它发挥作用，这样我就可以在不复制教授的解决方案的情况下取回分数。

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

Answer 1

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

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

aaobcc..ob..xxo...deeffpd..k.phh.k.p

If you make the correction to board::isSolved() from my comment:

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

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

10b dc lh rp up up uf rk uh lh r

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

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

一定要尝试抽象更多的细节。例如，也许您可​​以向 board 添加方法以 (1) 计算有效移动列表和 (2) 应用单个移动，返回新的 board。另外，如果您还没有学会如何使用调试器(如 gdb)，现在是开始学习的绝佳时机。参见 How do I use the MinGW gdb debugger to debug a C++ program in Windows?