推荐用于珠宝游戏的改进匹配查找算法？

Question

我试图确定一种为每一行和每列寻找3、4或5匹配的合理方法。玩家在棋盘中寻找区域(行或列)，其中相同的“宝石”将在交换两个相邻的部分(每个回合一个交换)后，重复3-5个连续的点。

下面是一个匹配操作的示例场景：

• 球员移动前的棋盘(必须用粗体交换)： A、C、B、B、C D-D-B-A-D D阿、阿、中、丙 A D B B A D C D A A
• 棋盘一个接一个的移动(粗体是最终的比赛)： A、C、B、B、C D D B A D D A、C、C D A B B A D C D A A

在这个例子中，在第一行之后的第一列中有一个4匹配的"D“。我正在努力弄清楚如何在1之后找到这样的匹配。)棋盘是在游戏开始时创建的，棋盘随机化了很多次，以消除直接的比赛，和2)。在玩家移动之后。如果工作正常，程序将能够在程序本身或播放机进行正确的交换后检测到匹配。

我尝试过的每一个算法都会导致循环超出界限和/或在交换后不正确地找到所有的结果匹配。我的意思是，程序有时会尝试在数组之外搜索，因为我没有成功地告诉程序如何“调整”它的数组搜索，根据当前位置搜索。即使它不会导致运行时错误，它仍然显示不正确的结果。例如，玩家将看到董事会至少有一个完整的匹配显示，这是不好的。

以下是我尝试过的两个步骤的解释：

• 跟踪空格.从当前的位置，检查，在前面检查同一行中的四个空格(如果行中剩余的空格少于四个)。首先检查5的匹配，包括当前的点；如果没有，则检查4个(减去一个点)；如果没有，则检查三个(减去一个点)；如果没有，则没有匹配。对在列下面重复相同的检查。
• 前面的空格。从当前位置的，检查同一行中的四个空格(如果行的第一个点和当前点之间的空格少于四个)。首先检查5的匹配，包括当前的点；如果没有，则检查4个(减去一个点)；如果没有，则检查三个(减去一个点)；如果没有，则没有匹配。对上的列重复相同的检查。

这里是需要这样的工作算法的主要函数。在这里使用我的Gem类(它已经被破坏了)对请求可能并不重要，所以我不会添加它，除非它是有用的。

bool Board::findMatches(bool scoringMove) // false if board is being setup before game
{
    bool matchesFound = false;

    // loops through entire board, where "size" is the width, not the number of spots
    for (int i = 0; i < size.getSize()*size.getSize(); i++)
    {
        // loops for each type of Gem, six total (_not identical to given example_)
        for (int k = 0; k < gems.getNumGems(); k++)
        {
            Gem traverseGems(k); // next Gem (in sequence)
            char nextGem = traverseGems.getGem(); // next Gem set to a char

            // ROWS check
            // default match search for 3-match
            if ((i < (size.getSize()*size.getSize())-4)
            && (board[i]->getGem() == nextGem)
            && (board[i+1]->getGem() == nextGem)
            && (board[i+2]->getGem() == nextGem))
            {
                // if the player is making a move
                if (!scoringMove)
                    return true;

                matchesFound = true;

                // just adds points to score; irrelevant to algorithm
                scoreMatches(3, 'R', i, 3);

                // no 4-match, but a 3-match
                if (board[i+3]->getGem() != nextGem)
                    scoreMatches(3, 'R', i, 3);
                else
                    scoreMatches(4, 'R', i, 4);

                // 5-match found
                if (board[i+3]->getGem() == nextGem && board[i+4]->getGem() == nextGem)
                    scoreMatches(5, 'R', i, 5);
            }

            // COLUMNS check (comments for rows check apply here as well)

            if ((i <= (size.getSize()-1))
            && (board[i]->getGem() == nextGem)
            && (board[i+size.getSize()]->getGem() == nextGem)
            && (board[i+(size.getSize()*2)]->getGem() == nextGem))
            {
                if (!scoringMove)
                    return true;

                matchesFound = true;

                scoreMatches(3, 'C', i, 3);

                if (board[i+(size*3)]->getGem() != nextGem)
                    scoreMatches(3, 'C', i, 3);
                else
                    scoreMatches(4, 'C', i, 4);
                if (board[i+(size*3)]->getGem() == nextGem && board[i+(size*4)]->getGem() == nextGem)
                    scoreMatches(5, 'C', i, 5);
            }
        }
    }

    return matchesFound;
}

Board.h

#ifndef BOARD_H
#define BOARD_H

#include "Size.h"
#include "Score.h"
#include "Move.h"
#include "Gem.h"

#include <iostream>
#include <iomanip>
#include <ctime>

class Board
{
private:
    Size size;
    Score score;
    Gem **board;
    bool moreSwaps;

    void swapGems(Move);
    void swapGems(int, int);
    void setNewRandGem(int);
    void findMoreSwaps();
    void scoreMatches(int, char, int, int);
    bool findMatches(bool);

public:
    Board();
    Board(Size, Score&);
    ~Board();
    void displayBoard() const;
    bool isMatch(Move);
    bool moreMovesFound() const;
};

#endif

板构造器

Board::Board(Size size, Score &score)
{
    srand((unsigned int)time(NULL)); // I can always move this to main()

    this->size = size;
    this->score = score;

    board = new Gem *[size.getSize()*size.getSize()];

    for (int i = 0; i < size.getSize()*size.getSize(); i++)
        board[i] = new Gem;

    //This is the "pre-game" block.
    //As long as the program finds a new match after performing its
    //own swaps, it'll randomize the entire board and start over again.
    //This is incredibly unefficient, but I will try to fix it later.
    do
    {
        for (int i = 0; i < size.getSize()*size.getSize(); i++)
            setNewRandGem(i);

    } while (findMatches(false));
}

Answer 1

重新阅读更新的问题后，我认为您的目标是测试，对于给定的5x5板，是否有可能交换两个相邻的符号，从而在一行或列中生成一个具有3个或更多相同符号的板。

如果以前的尝试产生了超出界限的错误，那就意味着实现中有错误，而不是算法中的错误。因此，使用不同的算法无法解决这个问题，您仍然需要实现适当的数组边界检查。这是没有办法的，但从好的方面来说，这并不是特别困难。在访问数组之前，只需检查每个索引是小于零还是大于数组维度大小。如果是的话，请追溯您的程序用于获取该值的步骤，并找到必须存在的bug。

当然，如果程序除了产生超出界限的错误之外，还会产生错误的结果，那么您的算法也可能是错误的。

尽管如此，我仍然不确定我是否理解您描述的算法，但是对于这个问题，它们看起来太复杂了。除非您需要评估数千块板每秒，一个简单的蛮力算法就足够了。只需尝试所有可能的交换，并对每个交换检查板是否在一行或列中包含3个或更多相同的符号。

下面是伪代码的描述：

function is_there_a_valid_move(board)
// returns true if there is a valid bejewelled move

   // test all horizontal swaps
   for (x = 0; x++; x< board-width - 1):
      for (y = 0; y++; y < board-height):
         make a copy of the board: board2
         swap board2[x,y] and board2[x+1,y]
         check_matches(board2, 3)
         if match found: return true

   // test all vertical swaps
   for (x = 0; x++; x< board-width):
      for (y = 0; y++; y < board-height - 1):
         make a copy of the board: board2
         swap board2[x,y] and board2[x,y+1]
         check_matches(board2, 3)
         if match found: return true

   return false

function check_matches(board, num_matches)
// returns true if there are num_matches or more of the same symbol in a row or column

   // check rows
   for (y = 0; y++; y < board-height):
      consecutive_symbols = 0
      for (x = 0; x++; x< board-width - 1):
         if board[x,y] == board[x+1,y]: consecutive_symbols++
         else: consecutive_symbols = 0
         if consecutive_symbols >=num_matches: return true

   // check columns
   for (x = 0; x++; x< board-width):
      consecutive_symbols = 0
      for (y = 0; y++; y < board-height - 1):
         if board[x,y] == board[x,y+1]: consecutive_symbols++
         else: consecutive_symbols = 0
         if consecutive_symbols >=num_matches: return true     

   return false

这当然不是最快的方法，但是对于5x5板来说，其他的一切都是过度的。