求助！关于递归调用的两个题目（五子棋和围棋）

Question

刚学JAVA，不甚了解，望高手指点一二
1.五子棋：10X10的棋盘（数组表示），用递归调用实现，能够判断出五子棋哪方获胜，即同种颜色的棋子五子连续(8个方向）。黑子用1表示，白字用－1，无子的用0表示。
2.围棋：也是10X10大小，编写一程序，判断基点棋子周围的棋子是否被吃掉，比如有黑棋围住了6颗白棋，那么这6颗白棋就都被吃掉有一类似例题，供各位参考：
ex：可以把相连的1都换成2。
public class Recursion2{ 
  int[][] map={{0, 0, 0, 0, 0, 0, 0, 1, 1, 0}, 
               {0, 1, 1, 1, 1, 1, 0, 1, 0, 0}, 
               {1, 0, 0, 0, 0, 1, 0, 0, 0, 0}, 
               {0, 0, 0, 0, 1, 1, 0, 0, 1, 1}, 
               {0, 1, 1, 0, 0, 1, 0, 0, 1, 0}, 
               {0, 0, 1, 1, 1, 1, 0, 0, 1, 0}, 
               {1, 0, 0, 0, 0, 1, 1, 1, 1, 0}, 
               {0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, 
               {0, 0, 1, 1, 1, 1, 1, 0, 0, 1}, 
               {1, 0, 0, 0, 0, 0, 0, 0, 1, 0} };   
  void checkXY(int x, int y){ 
    if(x>=0 && x<=9 && y>=0 && y<=9 && map[x][y]==1){ 
      map[x][y]=2; 
      check(x, y); 
    } 
  } 
  void check(int x, int y){ 
    if(map[x][y]==0)return ; 
    checkXY(x-1, y); 
    checkXY(x+1, y); 
    checkXY(x, y-1); 
    checkXY(x, y+1);   
  } 
  void printMap(){ 
    for(int i=0; i<10; i++){ 
      for(int j=0; j<10; j++) 
        System.out.print(map[i][j]); 
      System.out.println();     
    } 
  }        
  public static void main(String[] args){ 
    Recursion2 ob=new Recursion2(); 
    ob.check(1,3); 
    ob.printMap(); 
  } 
} 

Answer 1

public int check(int row, int col) {
int n = 0;  //记录多少个子相连
int color = getGridState(row, col);
if(!(color == MAN_WHITE || color == MAN_BLACK)) return WIN_PENDENCY;
//扫描方向：水平 ─
n = 1;
for(int i = 1; i < 5; i++) {
if(getGridState(row, col - i) == color) n++;
else break;
}
for(int i = 1; i < 5; i++) {
if(getGridState(row, col + i) == color) n++;
else break;
}
if(n >= 5) return (color == MAN_WHITE) ? WIN_WHITE : WIN_BLACK;
//扫描方向：垂直 │
n = 1;
for(int i = 1; i < 5; i++) {
if(getGridState(row + i, col) == color) n++;
else break;
}
for(int i = 1; i < 5; i++) {
if(getGridState(row - i, col) == color) n++;
else break;
}
if(n >= 5) return (color == MAN_WHITE) ? WIN_WHITE : WIN_BLACK;
//扫描方向：对角左上-右下 \
n = 1;
for(int i = 1; i < 5; i++) {
if(getGridState(row + i, col - i) == color) n++;
else break;
}
for(int i = 1; i < 5; i++) {
if(getGridState(row - i, col + i) == color) n++;
else break;
}
if(n >= 5) return (color == MAN_WHITE) ? WIN_WHITE : WIN_BLACK;
//扫描方向：对角右上-左下 /
n = 1;
for(int i = 1; i < 5; i++) {
if(getGridState(row + i, col + i) == color) n++;
else break;
}
for(int i = 1; i < 5; i++) {
if(getGridState(row - i, col - i) == color) n++;
else break;
}
if(n >= 5) return (color == MAN_WHITE) ? WIN_WHITE : WIN_BLACK;
//返回扫描结果
return WIN_PENDENCY;
}

Answer 2

其中  /** 棋局状态：未分胜负 */
public static final int WIN_PENDENCY = 0;
/** 棋局状态：黑方胜 */
public static final int WIN_BLACK = 1;
/** 棋局状态：白方胜 */
public static final int WIN_WHITE = -1;
/** 棋盘格子状态：无子 */
public static final int MAN_NULL = 0;
/** 棋盘格子状态：黑子 */
public static final int MAN_BLACK = 1;
/** 棋盘格子状态：白子 */
public static final int MAN_WHITE = -1;

Answer 3

算了，全贴了吧，楼主得有点耐性看完，一个较完整的五子棋棋盘类：/*
 * @(#)GobangBoard.java  0.5.6  2007/04/26
 * Author: SageZk
 */package com.stway.gobang;/**
 * GobangBoard 五子棋棋盘类。在五子棋游戏中，<code>GobangBoard</code> 的实例表示一张实际的棋盘。
 * 在实例内部，存储有棋盘上每个格子的状态，并提供了一些改变棋盘状态的方法，例如：
 * <code>getGridState</code>，另外还提供了一些简单的统计功能，
 * 例如：方法 <code>getCountOfBlackMan</code> 统计棋盘上黑子的数量。<p>
 * <code>public int checkWin(int row, int col)</code> 方法使用示例：<br>
 * <code><pre>scan:
 * for(int r = 0; r < getRows(); r++) {
 *     for(int c = 0; c < getCols(); c++) {
 *         switch(checkWin(r, c)) {
 *         case WIN_PENDENCY:
 *             break;
 *         case WIN_WHITE:
 *             System.out.println("白方胜，黑方负！");
 *             break scan;
 *         case WIN_BLACK:
 *             System.out.println("黑方胜，白方负！");
 *             break scan;
 *         }
 *     }
 * }</pre></code>
 * @version 0.5.6
 * @author SageZk
 */
public class GobangBoard implements Cloneable { //静态域------------------------------------------------------------------------------------- /** 黑棋子字符 */
public static final char CHAR_BLACK_MAN = '●';
/** 白棋子字符 */
public static final char CHAR_WHITE_MAN = '○';
/** 最后落子点黑棋子字符 */
public static final char CHAR_LAST_BLACK_MAN = '■';
/** 最后落子点白棋子字符 */
public static final char CHAR_LAST_WHITE_MAN = '□';
/** 棋局状态：未分胜负 */
public static final int WIN_PENDENCY = 0;
/** 棋局状态：黑方胜 */
public static final int WIN_BLACK = 1;
/** 棋局状态：白方胜 */
public static final int WIN_WHITE = -1;
/** 棋盘格子状态：无子 */
public static final int MAN_NULL = 0;
/** 棋盘格子状态：黑子 */
public static final int MAN_BLACK = 1;
/** 棋盘格子状态：白子 */
public static final int MAN_WHITE = -1; //实例域------------------------------------------------------------------------------------- private final int rows; //棋盘行数
private final int cols; //棋盘列数
private final int[][] gridState; //棋盘每个格子的落子状态
private Object locker = null; //锁定棋盘对象的引用
private int lastr = 0; //最后落子点的行下标
private int lastc = 0; //最后落子点的列下标 //构造方法----------------------------------------------------------------------------------- /**
 * 创建具有默认行数（15行）和默认列数（15列）的棋盘类实例。
 */
public GobangBoard() {
this(15, 15);
} /**
 * 创建具有指定行数（rows行）和指定列数（cols列）的棋盘类实例。
 * @param rows 指定创建的棋盘实例的行数。
 * @param cols 指定创建的棋盘实例的列数。
 */
public GobangBoard(int rows, int cols) {
//校验参数有效性
if(rows < 6) rows = 6;
else if(rows > 26) rows = 26;
if(cols < 6) cols = 6;
else if(cols > 26) cols = 26;
//初始化实例域
this.rows = rows;
this.cols = cols;
this.gridState = new int[this.rows][this.cols];
//整型二维数组元素默认初始值为0
for(int r = 0; r < this.gridState.length; r++) {
for(int c = 0; c < this.gridState[r].length; c++) {
this.gridState[r][c] = MAN_NULL;
}
}
//System.out.println("DebugInfo[this.rows = " + this.rows + ", this.cols = " + this.cols + "]");
//System.out.println("DebugInfo[this.gridState.length = " + this.gridState.length + ", this.gridState[0].length = " + this.gridState[0].length + "]");
} //实例方法----------------------------------------------------------------------------------- /*
 * 根据参数 man 统计并返回棋盘上空位、白子或黑子的数量。
 * @param man 要统计的内容，可以取 MAN_NONE、MAN_WHITE、MAN_BLACK 三个常量中的一个。
 * @return 返回统计结果。
 */
private int count(int man) {
if(!(man == MAN_NULL || man == MAN_WHITE || man == MAN_BLACK)) return -1;
int mn = 0;  //临时存储统计中的空位数量
int mw = 0;  //临时存储统计中的白子数量
int mb = 0;  //临时存储统计中的黑子数量
for(int r = 0; r < this.gridState.length; r++) {
for(int c = 0; c < this.gridState[r].length; c++) {
switch(this.gridState[r][c]) {
case MAN_NULL:
mn++;
break;
case MAN_WHITE:
mw++;
break;
case MAN_BLACK:
mb++;
break;
}
}
}
switch(man) {
case MAN_NULL:
return mn;
case MAN_WHITE:
return mw;
case MAN_BLACK:
return mb;
}
return -1;
} /**
 * 根据落子情况判断黑白双方胜负状态。
 * @param row 棋盘的行编号。
 * @param col 棋盘的列编号。
 * @return 返回 <code>WIN_PENDENCY</code>、<code>WIN_WHITE</code、
 *  <code>WIN_BLACK</code 三个常量值之一。
 */
public int check(int row, int col) {
int n = 0;  //记录多少个子相连
int color = getGridState(row, col);
if(!(color == MAN_WHITE || color == MAN_BLACK)) return WIN_PENDENCY;
//扫描方向：水平 ─
n = 1;
for(int i = 1; i < 5; i++) {
if(getGridState(row, col - i) == color) n++;
else break;
}
for(int i = 1; i < 5; i++) {
if(getGridState(row, col + i) == color) n++;
else break;
}
if(n >= 5) return (color == MAN_WHITE) ? WIN_WHITE : WIN_BLACK;
//扫描方向：垂直 │
n = 1;
for(int i = 1; i < 5; i++) {
if(getGridState(row + i, col) == color) n++;
else break;
}
for(int i = 1; i < 5; i++) {
if(getGridState(row - i, col) == color) n++;
else break;
}
if(n >= 5) return (color == MAN_WHITE) ? WIN_WHITE : WIN_BLACK;
//扫描方向：对角左上-右下 \
n = 1;
for(int i = 1; i < 5; i++) {
if(getGridState(row + i, col - i) == color) n++;
else break;
}
for(int i = 1; i < 5; i++) {
if(getGridState(row - i, col + i) == color) n++;
else break;
}
if(n >= 5) return (color == MAN_WHITE) ? WIN_WHITE : WIN_BLACK;
//扫描方向：对角右上-左下 /
n = 1;
for(int i = 1; i < 5; i++) {
if(getGridState(row + i, col + i) == color) n++;
else break;
}
for(int i = 1; i < 5; i++) {
if(getGridState(row - i, col - i) == color) n++;
else break;
}
if(n >= 5) return (color == MAN_WHITE) ? WIN_WHITE : WIN_BLACK;
//返回扫描结果
return WIN_PENDENCY;
} /**
 * 计算并返回棋盘的行数。
 * @return 返回棋盘的行数。
 */
public int getRows() {
return this.rows;
} /**
 * 计算并返回棋盘的列数。
 * @return 返回棋盘的列数。
 */
public int getCols() {
return this.cols;
} /**
 * 返回最后落子点的行编号。
 * @return 返回最后落子点的行编号。
 */
public int getLastPuttingRow() {
return this.lastr;
} /**
 * 返回最后落子点的列编号。
 * @return 返回最后落子点的列编号。
 */
public int getLastPuttingCol() {
return this.lastc;
} /**
 * 返回表示最后落子点的 <code>Point</code> 对象。
 * @return 返回表示最后落子点的 <code>Point</code> 对象。
 */
public Point getLastPuttingPoint() {
return new Point(this.lastr, this.lastc);
} /**
 * 返回棋盘的锁定状态。已锁定返回 <code>true</code>，否则返回 <code>false</code>。
 * @return 棋盘已锁定返回 <code>true</code>，否则返回 <code>false</code>。
 */
public boolean isLocked() {
return this.locker != null;
} /**
 * 锁定棋盘。当棋盘处在锁定状态时，不能通过 <code>setGridState</code> 和 <code>putMan</code>
 * 方法完成棋盘状态更改。但可以使用 <code>getGridState</code> 方法读取棋盘格子状态。
 * 如果棋盘已经处于锁定状态，则不能再次锁定棋盘。
 * @param locker 给棋盘加锁的对象的引用。
 * @return 返回加锁操作结果。如果加锁成功返回 <code>true</code>，否则返回 <code>false</code>。
 */
public boolean lock(Object locker) {
if(locker == null) return false;
if(isLocked()) return false;
this.locker = locker;
return true;
} /**
 * 解除棋盘锁定。当棋盘处在锁定状态时，不能通过 <code>setGridState</code> 和 <code>putMan</code>
 * 方法完成棋盘状态更改。但可以使用 <code>getGridState</code> 方法读取棋盘格子状态。
 * 如果棋盘已经处于解锁状态，则不能再次解除棋盘锁定。
 * 如果解锁者 locker 不是锁定棋盘者，解锁操作将失败。
 * @param locker 给棋盘加锁的对象的引用，如果 <code>locker</code> 为给棋盘加锁的对象则解锁成功。
 * @return 返回解除棋盘锁定操作结果。如果解锁成功返回 <code>true</code>，否则返回 <code>false</code>。
 */
public boolean unlock(Object locker) {
if(locker == null) return false;
if(this.locker != locker) return false;
this.locker = null;
return true;
} /**
 * 统计并返回棋盘上白子的数量。
 * @return 返回棋盘上白子的数量。
 */
public int getCountOfWhiteMan() {
return count(MAN_WHITE);
} /**
 * 统计并返回棋盘上黑子的数量。
 * @return 返回棋盘上黑子的数量。
 */
public int getCountOfBlackMan() {
return count(MAN_BLACK);
} /**
 * 统计并返回棋盘上可以落子的格子数量。
 * @return 返回棋盘上可以落子的格子数量。
 */
public int getCountOfBlank() {
return count(MAN_NULL);
}

Answer 4

接上面：
/**
 * 计算并返回指定行编号和指定列编号的格子的落子状态。
 * @param row 棋盘的行编号。
 * @param col 棋盘的列编号。
 * @return 返回指定棋盘格子的落子状态即 <code>MAN_NULL</code>、<code>MAN_WHITE</code>、
 *  <code>MAN_BLACK</code> 三个常量值之一。
 */
public int getGridState(int row, int col) {
//校验参数有效性
if(row <= 0) return 1024;
else if(row > this.rows) return 1024;
if(col <= 0) return 1024;
else if(col > this.cols) return 1024;
//计算返回值
return this.gridState[this.rows - row][col - 1];
} /**
 * 计算并返回指定行编号和指定列编号的格子的落子状态。
 * @param point 表示棋盘上指定的点的 <code>Point</code> 类实例的引用。
 * @return 返回指定棋盘格子的落子状态即 <code>MAN_NULL</code>、<code>MAN_WHITE</code>、
 *  <code>MAN_BLACK</code> 三个常量值之一。
 */
public int getGridState(Point point) {
if(point == null) return 1024;
return getGridState(point.getRow(), point.getCol());
} /**
 * 更新棋盘指定行和指定列的格子的落子状态。此操作要求棋盘处于解锁状态。
 * @param row 棋盘的行编号。
 * @param col 棋盘的列编号。
 * @param state 新的落子状态即 <code>MAN_NULL</code>、<code>MAN_WHITE</code>、
 *  <code>MAN_BLACK</code> 三个常量值之一。
 * @return 如果指定的行编号或列编号超出范围或棋盘处于锁定状态，即设置失败返回
 *  <code>false</code>，否则返回 <code>true</code>。
 */
public boolean setGridState(int row, int col, int state) {
//棋盘锁定校验
if(isLocked()) return false;
//校验参数有效性
if(row <= 0) return false;
else if(row > this.rows) return false;
if(col <= 0) return false;
else if(col > this.cols) return false;
//根据row和col更新棋盘状态
if(state == MAN_NULL || state == MAN_WHITE || state == MAN_BLACK) {
this.lastr = row;
this.lastc = col;
this.gridState[this.rows - row][col - 1] = state;
return true;
}
return false;
} /**
 * 更新棋盘指定行和指定列的格子的落子状态。此操作要求棋盘处于解锁状态。
 * @param point 表示棋盘上指定的点的 <code>Point</code> 类实例的引用。
 * @param state 新的落子状态即 <code>MAN_NULL</code>、<code>MAN_WHITE</code>、
 *  <code>MAN_BLACK</code> 三个常量值之一。
 * @return 如果指定的落子点超出棋盘范围或棋盘处于锁定状态，即设置失败返回
 *  <code>false</code>，否则返回 <code>true</code>。
 */
public boolean setGridState(Point point, int state) {
if(point == null) return false;
return setGridState(point.getRow(), point.getCol(), state);
} /**
 * 完成落子操作，返回操作结果。此操作要求棋盘处于解锁状态。
 * @param row 棋盘的行编号。
 * @param col 棋盘的列编号。
 * @param man 落子颜色 <code>MAN_WHITE</code>、<code>MAN_BLACK</code> 两个常量值之一。
 * @return 如果指定的行或列编号超出范围或棋盘处于锁定状态或此格已有子则返回
 *  <code>false</code>，否则落子成功返回 <code>true</code>。
 */
public boolean putMan(int row, int col, int man) {
if(man == MAN_NULL) return false;
boolean r = false;
if(getGridState(row, col) == MAN_NULL) {
r = setGridState(row, col, man);
}
return r;
} /**
 * 完成落子操作，返回操作结果。此操作要求棋盘处于解锁状态。
 * @param point 表示棋盘上指定的点的 <code>Point</code> 类实例的引用。
 * @param man 落子颜色 <code>MAN_WHITE</code>、<code>MAN_BLACK</code> 两个常量值之一。
 * @return 如果指定的落子点超出棋盘范围或棋盘处于锁定状态或此格已有子则返回
 *  <code>false</code>，否则落子成功返回 <code>true</code>。
 */
public boolean putMan(Point point, int man) {
if(point == null) return false;
return putMan(point.getRow(), point.getCol(), man);
} /**
 * 清理棋盘，使所有格子都回到无子状态。此操作要求棋盘处于解锁状态。
 * @return 如果棋盘处于锁定状态则返回 <code>false</code>，否则清理成功返回 <code>true</code>。
 */
public boolean clear() {
//棋盘锁定校验
if(isLocked()) return false;
for(int r = 0; r < this.gridState.length; r++) {
for(int c = 0; c < this.gridState[r].length; c++) {
this.gridState[r][c] = MAN_NULL;
}
}
return true;
} /**
 * 根据棋盘状态在 Shell 窗口打印棋盘。
 */
public void print() {
//打印棋盘上边框
System.out.println();
System.out.print("   ╔");
for(int c = 1; c <= this.cols; c++) System.out.print("╤");
System.out.print("╗\n");
//打印棋盘网格, 左右边框, 行编号
for(int r = this.rows; r > 0; r--) {
System.out.print((r < 10) ? (" 0" + r) : (" " + r));
System.out.print("╟");
for(int c = 1; c <= this.cols; c++) {
switch(getGridState(r, c)) {
case MAN_NULL:
System.out.print("┼");
//if(r % 2 == 0) System.out.print((c % 2 == 0) ? "╋" : "┿");
//else System.out.print((c % 2 == 0) ? "╂" : "┼");
break;
case MAN_BLACK:
if(r == this.lastr && c == this.lastc) {
System.out.print(CHAR_LAST_BLACK_MAN);
} else {
System.out.print(CHAR_BLACK_MAN);
}
break;
case MAN_WHITE:
if(r == this.lastr && c == this.lastc) {
System.out.print(CHAR_LAST_WHITE_MAN);
} else {
System.out.print(CHAR_WHITE_MAN);
}
break;
}
}
System.out.print("╢\n");
}
//打印棋盘下边框
System.out.print("   ╚");
for(int c = 1; c <= this.cols; c++) System.out.print("╧");
System.out.print("╝\n");
//打印棋盘列编号(A-Z)
System.out.print("     ");
//for(int c = 1; c <= this.cols; c++) System.out.print((char)('A' + c - 1) + " ");
for(int c = 1; c <= this.cols; c++) System.out.print((char)('ａ' + c - 1));
/*System.out.println();
System.out.print("     ");
for(int c = 1; c <= this.cols; c++) {
if(c % 2 != 0) {
System.out.print((c < 10) ? ("0" + c) : ("" + c));
} else {
System.out.print("  ");
}
}*/
System.out.println();
//System.out.println("DebugInfo[LastRow:" + this.lastr + ",LastCol:" + this.lastc + "]");
} /**
 * 创建并返回此棋盘的一个副本（深表复制）。创建一个大小和各个格子状态与此棋盘相同的新棋盘对象，并返回它的引用。
 * @return 返回此棋盘的一个克隆的副本，即克隆的新棋盘对象的引用。
 * @see java.lang.Object#clone()
 */
public Object clone() throws CloneNotSupportedException {
GobangBoard rb = new GobangBoard(this.rows, this.cols);
/*for (int r = 1; r <= this.rows; r++) {
for (int c = 1; c <= this.cols; c++) {
rb.gridState[r][c] = this.gridState[r][c];
}
} //因效率太低被弃用 */
for (int r = 0; r < this.rows; r++) {
for (int c = 0; c < this.cols; c++) {
rb.gridState[r][c] = this.gridState[r][c];
}
}
rb.lastr = this.lastr;
rb.lastc = this.lastc;
rb.locker = null;
return rb;
} /**
 * 比较此棋盘与指定的对象。当且仅当该参数不为 <code>null</code>，并且是表示与此对象
 * 相同的点的棋盘类对象时，结果才为 <code>true</code>。
 * @param otherBoard 与此棋盘进行比较的对象。
 * @return 如果棋盘对象等价则返回 <code>true</code>，否则返回 <code>false</code>。
 */
public boolean equals(Object otherBoard) {
if(this == otherBoard) return true;
if(otherBoard == null) return false;
//if(!(otherPoint instanceof GobangBoard)) return false;
if(this.getClass() != otherBoard.getClass()) return false;
GobangBoard other = (GobangBoard) otherBoard;
if (other.rows != this.rows || other.cols != this.cols) return false;
for (int r = 0; r < this.rows; r++) {
for (int c = 0; c < this.cols; c++) {
if (other.gridState[r][c] != this.gridState[r][c]) return false;
}
}
return true;
} /**
 * 返回此棋盘的字符串表示形式。此方法仅在进行调试的时候使用，不同实现之间所返回的字符串格式可能有所不同。
 * 返回的字符串可能为空，但不可能为 <code>null</code>。
 * @return 此棋盘的字符串表示形式。
 */
public String toString() {
StringBuilder str = new StringBuilder();
str.append(getClass().getName());
str.append("[rows=");
str.append(this.rows);
str.append(",cols=");
str.append(this.cols);
str.append(",blackMan=");
str.append(getCountOfBlackMan());
str.append(",whiteMan=");
str.append(getCountOfWhiteMan());
str.append(",isLocked=");
str.append(isLocked());
str.append(",lastPuttingRow=");
str.append(this.lastr);
str.append(",lastPuttingCol=");
str.append(this.lastc);
str.append(']');
return str.toString();
}}

Answer 5

谢谢LS，可是这个也太复杂了点，java我才学了一个月，有没简单一点的，拜托了

Answer 6

恩，debug了半天，不容易读懂了，谢谢sagezk ，但是有递归实现的方法么。就是参照那个例子来的。
还有个围棋更郁闷，继续等待高人。

Answer 7

sagezk  贴子好好好研究研究

Answer 8

如果要写 AI 棋手，并且要走 1 步分析 n 步棋，递归算法是肯定要用的，但简单的胜负判定不用那么麻烦，最简单最直接的算法往往效率最高。