random interviews: check if a piece is valid in a go game

发表于 | 分类于

Given a go board, check if a piece is alive or not.

1
2
3
XXX
X0X
XXX

is not alive

1
2
3
XXX
X0 X
XXXX

is still alive

Assume your piece is marked as 1, enemy’s pieces are marked as -1. Empty space is marked as 0.

解法1：DFS

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
public bool isAlive(int[][] board, int i, int j) {
	// Mark visited nodes as Integer.MAX_VALUE;
	if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == -1 || board[i][j] == Integer.MAX_VALUE) {
		return false;
	}	
	if (board[i][j] == 0) {
		return true;
	}
	board[i][j] = Integer.MAX_VALUE;
	return isAlive(board, i + 1, j) || isAlive(board, i - 1, j) || isAlive(board, i, j + 1) || isAlive(board, i, j - 1);
}