连接4检查赢取algorithm
我知道有关连接4检查赢了很多的问题。 问题是，大多数其他algorithm使我的程序有运行时错误，因为他们试图访问我的数组之外的索引。 我的algorithm是这样的：
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; } 计数是检查胜利的variables，如果计数等于或大于4，则表示它们应该是同一玩家的连续4个或更多的令牌。
问题：有时候，这个方法不是4个令牌，而是4个令牌，而其他时候当4个令牌都没有时，这个方法就不检查赢了。
看起来像你的代码是正确的水平和垂直的情况下。 棘手的部分是对angular线的情况。
让我们试试看：
对于绿线，您的起始行位置是0 … maxRow – 4.该列将是0 … startsRow –
伪代码：
// top-left to bottom-right - green diagonals for( 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 diagonals for( 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; } } }
你可以做相似的对angular线（从左下angular到右上angular）。
出于某种原因，我不太喜欢柜台，所以我这样做（它适用于不同尺寸的板子）。
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; }
因此，通过你的代码挖掘，似乎对angular线检查只能赢得一个方向（如果我添加一个标记到最低行和最低列会发生什么？）
相反，基本的检查algorithm始终是相同的过程，无论您检查哪个方向。
你需要一个起点（x / y）和x / y delta（移动的方向）。 你可以总结一下这个方法
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");
哪个输出…
Vertical Win Win Lose Horizontal Win Win Lose Diag Win Win Lose
现在，你可以总结下来…
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");
打印出来的东西像…
Vertical Win Win Horizontal Win Win Diag Win Win
我想补充一点，如果你连续提供了4个芯片的正确开始，这个方法只能工作。 例如，didWin（gridTable，1，3，3）将为您的水平检查提供false而不是true，因为循环只能检查一个方向。
目的不是要提供一个“全面的，开箱即用”的解决scheme，而是一个可以开发更广泛的解决scheme的概念（我的意思是，我讨厌人们实际上必须考虑的问题）。 我也是基于OP会知道最后一块放在哪里的意思，即出发点来devise解决scheme的。
通过稍微修改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));
并能够得到它的工作。 有时答案不是一个完整的解决scheme，而是一个把某人带到新地方的想法的种子;）
我进一步的提高将包括提供预期的连体片的数量，但我很确定这是一个增强，我真的不需要certificate;）
这是为我工作，它也没有采取，只要看起来：
这些是对x和o有行，列，对angular和反对angular的方法;
public static void checkVertO(){ if (board[0][0] == 'O' && board[1][0] == 'O' && board[2][0] == 'O' && board[3][0] == 'O' || board[1][0] == 'O' && board[2][0] == 'O' && board[3][0] == 'O' && board[4][0] == 'O' || board[2][0] == 'O' && board[3][0] == 'O' && board[4][0] == 'O' && board[5][0] == 'O' || board[0][1] == 'O' && board[1][1] == 'O' && board[2][1] == 'O' && board[3][1] == 'O' || board[1][1] == 'O' && board[2][1] == 'O' && board[3][1] == 'O' && board[4][1] == 'O' || board[2][1] == 'O' && board[3][1] == 'O' && board[4][1] == 'O' && board[5][1] == 'O' || board[0][2] == 'O' && board[1][2] == 'O' && board[2][2] == 'O' && board[3][2] == 'O' || board[1][2] == 'O' && board[2][2] == 'O' && board[3][2] == 'O' && board[4][2] == 'O' || board[2][2] == 'O' && board[3][2] == 'O' && board[4][2] == 'O' && board[5][2] == 'O' || board[0][3] == 'O' && board[1][3] == 'O' && board[2][3] == 'O' && board[3][3] == 'O' || board[1][3] == 'O' && board[2][3] == 'O' && board[3][3] == 'O' && board[4][3] == 'O' || board[2][3] == 'O' && board[3][3] == 'O' && board[4][3] == 'O' && board[5][3] == 'O' || board[0][4] == 'O' && board[1][4] == 'O' && board[2][4] == 'O' && board[3][4] == 'O' || board[1][4] == 'O' && board[2][4] == 'O' && board[3][4] == 'O' && board[4][4] == 'O' || board[2][4] == 'O' && board[3][4] == 'O' && board[4][4] == 'O' && board[5][4] == 'O' || board[0][5] == 'O' && board[1][5] == 'O' && board[2][5] == 'O' && board[3][5] == 'O' || board[1][5] == 'O' && board[2][5] == 'O' && board[3][5] == 'O' && board[4][5] == 'O' || board[2][5] == 'O' && board[3][5] == 'O' && board[4][5] == 'O' && board[5][5] == 'O' || board[0][6] == 'O' && board[1][6] == 'O' && board[2][6] == 'O' && board[3][6] == 'O' || board[1][6] == 'O' && board[2][6] == 'O' && board[3][6] == 'O' && board[4][6] == 'O'|| board[2][6] == 'O' && board[3][6] == 'O' && board[4][6] == 'O' && board[5][6] == 'O'){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } } public static void checkHorzO(){ if (board[0][0] == 'O' && board[0][1] == 'O' && board[0][2] == 'O' && board[0][3] == 'O' || board[0][1] == 'O' && board[0][2] == 'O' && board[0][3] == 'O' && board[0][4] == 'O' || board[0][2] == 'O' && board[0][3] == 'O' && board[0][4] == 'O' && board[0][5] == 'O' || board[0][3] == 'O' && board[0][4] == 'O' && board[0][5] == 'O' && board[0][6] == 'O' || board[1][0] == 'O' && board[1][1] == 'O' && board[1][2] == 'O' && board[1][3] == 'O' || board[1][1] == 'O' && board[1][2] == 'O' && board[1][3] == 'O' && board[1][4] == 'O' || board[1][2] == 'O' && board[1][3] == 'O' && board[1][4] == 'O' && board[1][5] == 'O' || board[1][3] == 'O' && board[1][4] == 'O' && board[1][5] == 'O' && board[1][6] == 'O' || board[2][0] == 'O' && board[2][1] == 'O' && board[2][2] == 'O' && board[2][3] == 'O' || board[2][1] == 'O' && board[2][2] == 'O' && board[2][3] == 'O' && board[2][4] == 'O' || board[2][2] == 'O' && board[2][3] == 'O' && board[2][4] == 'O' && board[2][5] == 'O' || board[2][3] == 'O' && board[2][4] == 'O' && board[2][5] == 'O' && board[2][6] == 'O' || board[3][0] == 'O' && board[3][1] == 'O' && board[3][2] == 'O' && board[3][3] == 'O' || board[3][1] == 'O' && board[3][2] == 'O' && board[3][3] == 'O' && board[3][4] == 'O' || board[3][2] == 'O' && board[3][3] == 'O' && board[3][4] == 'O' && board[3][5] == 'O' || board[3][3] == 'O' && board[3][4] == 'O' && board[3][5] == 'O' && board[3][6] == 'O' || board[4][0] == 'O' && board[4][1] == 'O' && board[4][2] == 'O' && board[4][3] == 'O' || board[4][1] == 'O' && board[4][2] == 'O' && board[4][3] == 'O' && board[4][4] == 'O' || board[4][2] == 'O' && board[4][3] == 'O' && board[4][4] == 'O' && board[4][5] == 'O' || board[4][3] == 'O' && board[4][4] == 'O' && board[4][5] == 'O' && board[4][6] == 'O' || board[5][0] == 'O' && board[5][1] == 'O' && board[5][2] == 'O' && board[5][3] == 'O' || board[5][1] == 'O' && board[5][2] == 'O' && board[5][3] == 'O' && board[5][4] == 'O' || board[5][2] == 'O' && board[5][3] == 'O' && board[5][4] == 'O' && board[5][5] == 'O' || board[5][3] == 'O' && board[5][4] == 'O' && board[5][5] == 'O' && board[5][6] == 'O' ){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } } public static void checkHorzX(){ if (board[0][0] == 'X' && board[0][1] == 'X' && board[0][2] == 'X' && board[0][3] == 'X' || board[0][1] == 'X' && board[0][2] == 'X' && board[0][3] == 'X' && board[0][4] == 'X' || board[0][2] == 'X' && board[0][3] == 'X' && board[0][4] == 'X' && board[0][5] == 'X' || board[0][3] == 'X' && board[0][4] == 'X' && board[0][5] == 'X' && board[0][6] == 'X' || board[1][0] == 'X' && board[1][1] == 'X' && board[1][2] == 'X' && board[1][3] == 'X' || board[1][1] == 'X' && board[1][2] == 'X' && board[1][3] == 'X' && board[1][4] == 'X' || board[1][2] == 'X' && board[1][3] == 'X' && board[1][4] == 'X' && board[1][5] == 'X' || board[1][3] == 'X' && board[1][4] == 'X' && board[1][5] == 'X' && board[1][6] == 'X' || board[2][0] == 'X' && board[2][3] == 'X' && board[2][4] == 'X' && board[2][5] == 'X' || board[2][3] == 'X' && board[2][4] == 'X' && board[2][5] == 'X' && board[2][6] == 'X' || board[3][0] == 'X' && board[3][1] == 'X' && board[3][2] == 'X' && board[3][3] == 'X' || board[3][1] == 'X' && board[3][2] == 'X' && board[3][3] == 'X' && board[3][4] == 'X' || board[3][2] == 'X' && board[3][3] == 'X' && board[3][4] == 'X' && board[3][5] == 'X' || board[3][3] == 'X' && board[3][4] == 'X' && board[3][5] == 'X' && board[3][6] == 'X' || board[4][0] == 'X' && board[4][3] == 'X' && board[4][4] == 'X' && board[4][5] == 'X' || board[4][3] == 'X' && board[4][4] == 'X' && board[4][5] == 'X' && board[4][6] == 'X' || board[5][0] == 'X' && board[5][1] == 'X' && board[5][2] == 'X' && board[5][3] == 'X' || board[5][1] == 'X' && board[5][2] == 'X' && board[5][3] == 'X' && board[5][4] == 'X' || board[5][2] == 'X' && board[5][3] == 'X' && board[5][4] == 'X' && board[5][5] == 'X' || board[5][3] == 'X' && board[5][4] == 'X' && board[5][5] == 'X' && board[5][6] == 'X' ){ System.out.println("Game over, X won."); printBoard(); doIt(); }else { return; } } public static void checkDiagX(){ if (board[2][0] == 'X' && board[3][1] == 'X' && board[4][2] == 'X' && board[5][3] == 'X'|| board[1][0] == 'X' && board[2][1] == 'X' && board[3][2] == 'X' && board[4][3] == 'X'|| board[0][0] == 'X' && board[1][1] == 'X' && board[2][2] == 'X' && board[3][3] == 'X'|| board[0][1] == 'X' && board[1][2] == 'X' && board[2][3] == 'X' && board[3][4] == 'X'|| board[1][1] == 'X' && board[2][2] == 'X' && board[3][3] == 'X' && board[4][4] == 'X'|| board[2][1] == 'X' && board[3][2] == 'X' && board[4][3] == 'X' && board[5][4] == 'X'|| board[0][2] == 'X' && board[1][3] == 'X' && board[2][4] == 'X' && board[3][5] == 'X'|| board[1][2] == 'X' && board[2][3] == 'X' && board[3][4] == 'X' && board[4][5] == 'X'|| board[2][2] == 'X' && board[3][3] == 'X' && board[4][4] == 'X' && board[5][5] == 'X'|| board[0][3] == 'X' && board[1][4] == 'X' && board[2][5] == 'X' && board[3][6] == 'X'|| board[1][3] == 'X' && board[2][4] == 'X' && board[3][5] == 'X' && board[4][6] == 'X'|| board[2][3] == 'X' && board[3][4] == 'X' && board[4][5] == 'X' && board[5][6] == 'X'){ System.out.println("Game over, X won."); printBoard(); doIt(); }else { return; } } public static void checkDiagO(){ if (board[2][0] == 'O' && board[3][1] == 'O' && board[4][2] == 'O' && board[5][3] == 'O'|| board[1][0] == 'O' && board[2][1] == 'O' && board[3][2] == 'O' && board[4][3] == 'O'|| board[0][0] == 'O' && board[1][1] == 'O' && board[2][2] == 'O' && board[3][3] == 'O'|| board[0][1] == 'O' && board[1][2] == 'O' && board[2][3] == 'O' && board[3][4] == 'O'|| board[1][1] == 'O' && board[2][2] == 'O' && board[3][3] == 'O' && board[4][4] == 'O'|| board[2][1] == 'O' && board[3][2] == 'O' && board[4][3] == 'O' && board[5][4] == 'O'|| board[0][2] == 'O' && board[1][3] == 'O' && board[2][4] == 'O' && board[3][5] == 'O'|| board[1][2] == 'O' && board[2][3] == 'O' && board[3][4] == 'O' && board[4][5] == 'O'|| board[2][2] == 'O' && board[3][3] == 'O' && board[4][4] == 'O' && board[5][5] == 'O'|| board[0][3] == 'O' && board[1][4] == 'O' && board[2][5] == 'O' && board[3][6] == 'O'|| board[1][3] == 'O' && board[2][4] == 'O' && board[3][5] == 'O' && board[4][6] == 'O'|| board[2][3] == 'O' && board[3][4] == 'O' && board[4][5] == 'O' && board[5][6] == 'O'){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } } public static void checkAntiDiagX(){ if (board[3][0] == 'X' && board[2][1] == 'X' && board[1][2] == 'X' && board[0][3] == 'X'|| board[4][0] == 'X' && board[3][1] == 'X' && board[2][2] == 'X' && board[1][3] == 'X'|| board[3][1] == 'X' && board[2][2] == 'X' && board[1][3] == 'X' && board[0][4] == 'X'|| board[5][0] == 'X' && board[4][1] == 'X' && board[3][2] == 'X' && board[2][3] == 'X'|| board[4][1] == 'X' && board[3][2] == 'X' && board[2][3] == 'X' && board[1][4] == 'X'|| board[3][2] == 'X' && board[2][2] == 'X' && board[1][4] == 'X' && board[0][5] == 'X'|| board[5][1] == 'X' && board[4][2] == 'X' && board[3][3] == 'X' && board[2][4] == 'X'|| board[4][2] == 'X' && board[3][3] == 'X' && board[2][4] == 'X' && board[1][5] == 'X'|| board[3][3] == 'X' && board[2][4] == 'X' && board[1][5] == 'X' && board[0][6] == 'X'|| board[5][2] == 'X' && board[4][3] == 'X' && board[3][4] == 'X' && board[2][5] == 'X'|| board[4][3] == 'X' && board[3][4] == 'X' && board[2][5] == 'X' && board[1][6] == 'X'|| board[5][3] == 'X' && board[4][4] == 'X' && board[3][5] == 'X' && board[2][6] == 'X'){ System.out.println("Game over, X won."); printBoard(); doIt(); }else { return; } } public static void checkAntiDiagO(){ if (board[3][0] == 'O' && board[2][1] == 'O' && board[1][2] == 'O' && board[0][3] == 'O'|| board[4][0] == 'O' && board[3][1] == 'O' && board[2][2] == 'O' && board[1][3] == 'O'|| board[3][1] == 'O' && board[2][2] == 'O' && board[1][3] == 'O' && board[0][4] == 'O'|| board[5][0] == 'O' && board[4][1] == 'O' && board[3][2] == 'O' && board[2][3] == 'O'|| board[4][1] == 'O' && board[3][2] == 'O' && board[2][3] == 'O' && board[1][4] == 'O'|| board[3][2] == 'O' && board[2][2] == 'O' && board[1][4] == 'O' && board[0][5] == 'O'|| board[5][1] == 'O' && board[4][2] == 'O' && board[3][3] == 'O' && board[2][4] == 'O'|| board[4][2] == 'O' && board[3][3] == 'O' && board[2][4] == 'O' && board[1][5] == 'O'|| board[3][3] == 'O' && board[2][4] == 'O' && board[1][5] == 'O' && board[0][6] == 'O'|| board[5][2] == 'O' && board[4][3] == 'O' && board[3][4] == 'O' && board[2][5] == 'O'|| board[4][3] == 'O' && board[3][4] == 'O' && board[2][5] == 'O' && board[1][6] == 'O'|| board[5][3] == 'O' && board[4][4] == 'O' && board[3][5] == 'O' && board[2][6] == 'O'){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } }
