Jam*_*mal 8 c++ arrays algorithm search
我正在尝试确定一种合理的方法,可以为每个行和列找到3,4或5的匹配.在交换两个相邻的棋子(每回合一次交换)后,玩家在游戏板中寻找相同"宝石"所在的区域(行或列),重复3-5个连续点.
以下是匹配制作移动的示例场景:
玩家移动前的棋盘(粗体是必要的交换):
ACBBC
DDBAD
DAACC
AD BBA
DCDAA
玩家移动后的棋盘(粗体结果匹配):
ACBBC
D DBAD
D AACC
D ABBA
D CDAA
在此示例中,在第一行之后的第一列中存在"D"的4匹配.我试图弄清楚如何在1)之后找到这样的比赛.棋盘在比赛开始时创建并且棋盘随机化多次以消除即时比赛,以及2.)在球员移动之后.如果工作正常,程序本身或播放器正确交换后,程序将能够检测到匹配.
我尝试过的每个算法都会导致循环超出界限和/或在交换后不正确地找到所有匹配的匹配项.通过这个,我的意思是该程序有时会尝试在数组外搜索,因为我没有成功告诉程序如何根据当前点的位置"调整"其数组搜索.即使它不会导致运行时错误,它仍然会显示不正确的结果.例如,玩家将看到该板至少显示了一个完整的匹配,这是不好的.
以下是我尝试的两个程序的解释:
以下空格.从目前的点,检查前面四个空格横跨在同一行(或更少,如果有剩余的排在不到四个空格).首先检查五场比赛,包括当前比赛; 如果没有,检查四(减去一个点); 如果没有,请检查三个(减去一个点); 如果没有,则找不到匹配项.对以下列重复相同的检查.
前面的空间. 从目前的点,检查背部四个空格横跨在同一行(或更少,如果没有在该行中的第一地点与目前现货之间的不到四个空格).首先检查五场比赛,包括当前比赛; 如果没有,检查四(减去一个点); 如果没有,请检查三个(减去一个点); 如果没有,则找不到匹配项.对上面的列重复相同的检查.
这是需要这种工作算法的主要功能.在这里使用我的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));
}
重新阅读更新后的问题后，我认为您的目标是测试对于给定的 5x5 棋盘，是否存在任何可能交换两个相邻符号的可能性，从而产生一行或列中有 3 个或更多相同符号的棋盘。
如果之前的尝试产生了越界错误，则意味着实现中存在错误，而不是算法中的错误。因此，使用不同的算法无法解决该问题，您仍然需要实现适当的数组边界检查。没有办法解决这个问题，但从好的方面来说，这并不是特别困难。在访问数组之前，只需检查每个索引是否小于零或大于数组维度大小。如果是，请回溯您的程序用于获得该值的步骤，并找到必须存在的错误。
当然，如果程序除了越界错误还产生错误的结果，那么你的算法也可能是错误的。
话虽如此，我仍然不确定我是否理解您描述的算法，但它们对于这个问题来说似乎太复杂了。除非您需要每秒评估数千块板，否则简单的蛮力算法就足够了。只需尝试所有可能的交换，并为每次交换检查板上的行或列中是否包含 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 板来说，其他一切都太过分了。