我基本上有一个游戏板,玩家不能多次移动到同一个地方,否则你就输了。 玩家只能移动 -1、+1、-16 或 +16。 我想使用最小最大值来解决这个问题,并接收最小最大值使用的输入,以便我可以看到它是如何完成的。
这是我目前的做法
#pragma optimize("", off)
#include <stdio.h>
#include <Windows.h>
#define hitcount 4
#define POINT 1
#define MINE 2
#define END 3
//4 targets: hit all 1's
//player/mine is 2
//game ender is 3
int Board[] = {
0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 1, 0,
2, 0, 0, 1, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0,
3, 0, 0, 0, 0, 0, 0
};
static const int choices[] = {
-1, 1, -16, 16
};
struct mb {
int end;
int score;
int* moveset;
};
mb solve(int Position, int *Board, int BoardSize, int *MoveSet = NULL, int Offset = 0, int Choice = 0, int Score = 0, bool tree = true) {
if( tree ) { //tree
int *BoardCopy = new int[BoardSize];
for( int i = 0; i < sizeof(choices); i++ ) {
MoveSet = new int[256];
for( int i = 0; i < 256; i++ )
MoveSet[i] = 0xFF;
memcpy(BoardCopy, Board, BoardSize);
mb m = solve(Position, BoardCopy, BoardSize, MoveSet, Offset, i, Score, false);
if( m.moveset != NULL ) {
if( m.end == 1 && m.score == hitcount ) {
delete[] BoardCopy;
return m;
}
}
delete[] MoveSet; //this is apparently causing problems??
}
delete[] BoardCopy;
}
else { //branch
mb m = {0, 0, MoveSet};
Position += choices[Choice];
m.moveset[Offset] = choices[Choice];
if( Position < 0 || Position >= BoardSize || Board[Position] == MINE || (Board[Position] == END && Score != hitcount) ) {
m.moveset = NULL;
return m;
}
else if( Board[Position] == POINT ) {
m.score++;
}
else if( Board[Position] == END ) {
m.end = 1;
return m;
}
Board[Position] = MINE;
return solve(Position, Board, BoardSize, m.moveset, Offset + 1, Choice + 1, m.score);
}
mb m = {0, 0, NULL};
return m;
}
int main() {
int Position = 0;
for( int i = 0; i < sizeof(Board); i++ ) {
if( Board[i] == MINE ) Position = i;
}
mb m = solve(Position, Board, sizeof(Board));
if( m.end == 1 && m.moveset != NULL && m.score == hitcount ) {
printf("SUCCESS!n");
}
getchar();
return 0;
}
但是,它不起作用。 我不知道为什么。 该算法看起来应该可以工作,而我的问题看起来与内存清理有关。 我的VC++工作室断点在调用后_CrtIsValidHeapPtr解决几次
我无法证明算法的正确性。但是,有些编码错误将导致您应该解决的未定义行为。
主要问题是您将数组的大小与数组中的元素数量混淆了。在你的main()
中,你应该用sizeof(Board)/sizeof(*Board)
来确定Board
数组元素的数量,否则你会在数组边界之外读取Board
。然后,您将sizeof(Board)
作为BoardSize
传递给solve
,但同样,当您检查Position
是否在范围内时,这不是使用的正确值。外部for
循环还会错误地计算choices
数组元素的数量。
作为次要问题,您将在 solve()
的内部for
循环中用另一个名为 i
的变量掩盖了 i
循环变量名称。为了避免混淆,它可能应该重命名。
因此,考虑到这些,我会在main()
中进行更改:
for( int i = 0; i < sizeof(Board)/sizeof(*Board); i++ ) {
if( Board[i] == MINE ) Position = i;
}
mb m = solve(Position, Board, sizeof(Board)/sizeof(*Board));
然后,我会改变solve()
:
for( int i = 0; i < sizeof(choices)/sizeof(*choices); i++ ) {
MoveSet = new int[256];
for( int j = 0; j < 256; j++ )
MoveSet[j] = 0xFF;
memcpy(BoardCopy, Board, BoardSize*sizeof(int));
此外,您可以通过对BoardCopy
和MoveSet
使用 std::vector<int>
来相当轻松地避免代码中的new/delete
业务。例如:
std::vector<int> BoardCopy(BoardSize);
//...
std::copy(Board, Board+BoardSize, BoardCopy.begin());
要像在代码中一样传入int *
参数,您需要传入&BoardCopy[0]
,但您应该考虑修改代码以采用std::vector<int> &
。 执行此操作时,可以删除对 delete BoardCopy
的所有调用。