连接4检查获胜算法
我知道有很多关于Connect 4 Check获胜的问题。问题在于大多数其他算法使我的程序出现运行时错误，因为它们尝试访问数组之外的索引。我的算法是这样的：
private int checkWin(int[][] gridTable,int rowNum,int colNum, int maxRow, int maxCol)
{
// For checking whether any win or lose condition is reached. Returns 1 if win or lose is reached. else returns 0
// gridTable[][] is the game matrix(can be any number of rows and columns between 4 and 40)
// colNum is the column number where the last token was placed
// rowNum is the row number where the last token was placed
// maxRow is the number of rows in my grid
// maxCol is the number of columns in my grid
int player = gridTable[rowNum][colNum]; //player ID
int count=0;
// Horizontal check
for (int i=0;i<maxCol;i++)
{
if (gridTable[rowNum][i]==player)
count++;
else
count=0;
if (count>=4)
return 1;
}
//Vertical check
for (int i=0;i<maxRow;i++)
{
if (gridTable[i][colNum]==player)
count++;
else
count=0;
if (count>=4)
return 1;
}
count=0;
// 4 in a row diagonally
for(int i=colNum+1,j=rowNum+1;i<maxRow && j<maxCol;i++,j++)
{
if(gridTable[j][i]!=player)
{
count=1;
break;
}
count++;
}
// 4 in a row diagonally
for(int i=colNum-1,j=rowNum-1;i>=0 && j>=0;i--,j--)
{
if(gridTable[j][i]!=player)
{
count=1;
break;
}
count++;
}
// 4 in a row diagonally
for(int i=colNum+1,j=rowNum-1;i<maxRow && j>=0;i++,j--)
{
if(gridTable[j][i]!=player)
{
count=1;
break;
}
count++;
}
for(int i=colNum-1,j=rowNum+1;i>=0 && j<maxCol;i--,j++)
{ // 4 in a row diagonally
if(gridTable[j][i]!=player)
{
count=1;
break;
}
count++;
}
if(count>=4)
return 1;
return 0;
}
count是用于检查是否等于或大于4的胜利的变量，这意味着它们应为同一玩家的4个或更多连续标记。
问题：有时该方法检查获胜的顺序是否为4个令牌，而有时不检查获胜的顺序为4个令牌。
千巷猫影浏览 621回答 3
3回答
-
凤凰求蛊
看起来您的代码对于水平和垂直情况都是正确的。棘手的部分是对角线情况。让我们尝试一下图片：在此处输入图片说明对于绿线，您的起始行位置为0 ... maxRow-4。该列将为0 ... startingRow-伪代码：// top-left to bottom-right - green diagonalsfor( rowStart = 0; rowStart < rowMax - 4; rowStart++){ count = 0; int row, col; for( row = rowStart, col = 0; row < rowMax && col < colMax; row++, col++ ){ if(gridTable[row][col] == player){ count++; if(count >= 4) return 1; } else { count = 0; } }}// top-left to bottom-right - red diagonalsfor( colStart = 1; colStart < colMax - 4; rowStart++){ count = 0; int row, col; for( row = 0, col = colStart; row < rowMax && col < colMax; row++, col++ ){ if(gridTable[row][col] == player){ count++; if(count >= 4) return 1; } else { count = 0; } }}对于对角线的另一种方式（从左下到右上），您可以执行类似的操作。 -
ibeautiful
由于某种原因，我不喜欢计数器，所以我这样做（它适用于不同尺寸的电路板）。public boolean areFourConnected(int player){ // horizontalCheck for (int j = 0; j<getHeight()-3 ; j++ ){ for (int i = 0; i<getWidth(); i++){ if (this.board[i][j] == player && this.board[i][j+1] == player && this.board[i][j+2] == player && this.board[i][j+3] == player){ return true; } } } // verticalCheck for (int i = 0; i<getWidth()-3 ; i++ ){ for (int j = 0; j<this.getHeight(); j++){ if (this.board[i][j] == player && this.board[i+1][j] == player && this.board[i+2][j] == player && this.board[i+3][j] == player){ return true; } } } // ascendingDiagonalCheck for (int i=3; i<getWidth(); i++){ for (int j=0; j<getHeight()-3; j++){ if (this.board[i][j] == player && this.board[i-1][j+1] == player && this.board[i-2][j+2] == player && this.board[i-3][j+3] == player) return true; } } // descendingDiagonalCheck for (int i=3; i<getWidth(); i++){ for (int j=3; j<getHeight(); j++){ if (this.board[i][j] == player && this.board[i-1][j-1] == player && this.board[i-2][j-2] == player && this.board[i-3][j-3] == player) return true; } } return false;} -
Helenr
因此，浏览完您的代码后，似乎对角线检查只能在一个方向上获胜（如果我在最低行和最低列中添加标记，会发生什么情况？）而是，基本检查算法始终是相同的过程，而不管您要检查的方向是什么。您需要一个起点（x / y）和x / y增量（运动方向）。您可以将其归纳为一个方法...public boolean didWin(int[][] grid, int check, int row, int col, int rowDelta, int colDelta) { boolean win = true; for (int count = 0; count < 4; count++) { if (row < ROWS && row >= 0 && col < COLUMNS && col >= 0) { int test = grid[row][col]; if (test != check) { win = false; break; } } row += rowDelta; col += colDelta; } return win;}基本上，您可以从四个方向检查，也可以向后检查所以，如果我们要使用类似...int[][] gridTable = new int[ROWS][COLUMNS];gridTable[ROWS - 1][3] = 1;gridTable[ROWS - 2][3] = 1;gridTable[ROWS - 3][3] = 1;gridTable[ROWS - 4][3] = 1;System.out.println("Vertical");System.out.println(didWin(gridTable, 1, ROWS - 4, 3, 1, 0) ? "Win" : "Lose");System.out.println(didWin(gridTable, 1, ROWS - 1, 3, -1, 0) ? "Win" : "Lose");System.out.println(didWin(gridTable, 1, 0, 3, 1, 0) ? "Win" : "Lose");gridTable = new int[ROWS][COLUMNS];gridTable[3][1] = 1;gridTable[3][2] = 1;gridTable[3][3] = 1;gridTable[3][4] = 1;System.out.println("");System.out.println("Horizontal");System.out.println(didWin(gridTable, 1, 3, 1, 0, 1) ? "Win" : "Lose");System.out.println(didWin(gridTable, 1, 3, 4, 0, -1) ? "Win" : "Lose");System.out.println(didWin(gridTable, 1, 3, 0, 0, 1) ? "Win" : "Lose");gridTable = new int[ROWS][COLUMNS];gridTable[0][1] = 1;gridTable[1][2] = 1;gridTable[2][3] = 1;gridTable[3][4] = 1;System.out.println("");System.out.println("Diag");System.out.println(didWin(gridTable, 1, 0, 1, 1, 1) ? "Win" : "Lose");System.out.println(didWin(gridTable, 1, 3, 4, -1, -1) ? "Win" : "Lose");System.out.println(didWin(gridTable, 1, 1, 2, 1, 1) ? "Win" : "Lose");哪个输出...VerticalWinWinLoseHorizontalWinWinLoseDiagWinWinLose现在，您可以将其总结为...public boolean didWin(int[][] grid, int check, int row, int col) { return didWin(grid, check, row, col, 1, 0) || didWin(grid, check, row, col, -1, 0) || didWin(grid, check, row, col, 0, 1) || didWin(grid, check, row, col, 0, -1) || didWin(grid, check, row, col, 1, 1) || didWin(grid, check, row, col, -1, -1) || didWin(grid, check, row, col, -1, 1) || didWin(grid, check, row, col, 1, -1);}因此，使用类似...int[][] gridTable = new int[ROWS][COLUMNS];gridTable[ROWS - 1][3] = 1;gridTable[ROWS - 2][3] = 1;gridTable[ROWS - 3][3] = 1;gridTable[ROWS - 4][3] = 1;System.out.println("Vertical");System.out.println(didWin(gridTable, 1, ROWS - 1, 3) ? "Win" : "Lose");System.out.println(didWin(gridTable, 1, ROWS - 4, 3) ? "Win" : "Lose");gridTable = new int[ROWS][COLUMNS];gridTable[3][1] = 1;gridTable[3][2] = 1;gridTable[3][3] = 1;gridTable[3][4] = 1;System.out.println("");System.out.println("Horizontal");System.out.println(didWin(gridTable, 1, 3, 1) ? "Win" : "Lose");System.out.println(didWin(gridTable, 1, 3, 4) ? "Win" : "Lose");gridTable = new int[ROWS][COLUMNS];gridTable[0][1] = 1;gridTable[1][2] = 1;gridTable[2][3] = 1;gridTable[3][4] = 1;System.out.println("");System.out.println("Diag");System.out.println(didWin(gridTable, 1, 0, 1) ? "Win" : "Lose");System.out.println(didWin(gridTable, 1, 3, 4) ? "Win" : "Lose");哪个打印出类似...VerticalWinWinHorizontalWinWinDiagWinWin我要补充一点，这种方法仅在您连续提供4个芯片的正确开始时才有效。例如didWin（gridTable，1，3，3）将为水平检查提供false而不是true，因为循环只能检查一个方向。这样做的目的不是提供“完整的，即装即用的”解决方案，而是提供一个可以开发更广泛的解决方案的概念（我是说，我讨厌人们实际上不得不思考；）。我还基于以下想法设计了解决方案：OP将知道最后一块放置在哪里，即起点；）通过didWin稍微修改一下方法，就可以从任何点检查n逐个n网格...public boolean didWin(int[][] grid, int check, int row, int col, int rowDelta, int colDelta) { boolean match = false; int matches = 0; while (row < ROWS && row >= 0 && col < COLUMNS && col >= 0) { int test = grid[row][col]; if (test != check && match) { break; } else if (test == check) { match = true; matches++; } row += rowDelta; col += colDelta; } return matches == 4;}所以，我用...public static final int ROWS = 8;public static final int COLUMNS = 8;//...int[][] gridTable = new int[ROWS][COLUMNS];gridTable[ROWS - 1][3] = 1;gridTable[ROWS - 2][3] = 1;gridTable[ROWS - 3][3] = 1;gridTable[ROWS - 4][3] = 1;for (int[] row : gridTable) { StringJoiner sj = new StringJoiner("|", "|", "|"); for (int col : row) { sj.add(Integer.toString(col)); } System.out.println(sj);}System.out.println(didWin(gridTable, 1, 3, 3));并能够使其正常工作。有时答案不是一个完整的解决方案，而是将某人带到新地方的想法的种子；）我将进一步增强功能，包括提供预期的连接件数量，但是我很确定这是我真的不需要演示的增强功能；）
随时随地看视频慕课网APP
Java
数学
算法与数据结构