題目連結: Find Winner on a Tic Tac Toe Game

題目描述為: 給定一個二維陣列，來表示玩家 A,B 進行的井字遊戲過程，要我們判斷遊戲狀態: A贏/B贏/平手/尚未結束。 其中由玩家 A 先開始，以"X" 記號表示行動， 玩家 B 記號為 "O"。

思路 1: 按照定義轉換

我們可以按照定義遍歷所有元素，將其轉換成一組 3x3 的字串陣列，再檢查是否有玩家達成 直線/橫線/對角線 的連線，來判定遊戲狀態。

• 複雜度評估
  井字遊戲的玩法為固定3x3大小，因此我們遍歷轉換的步驟也是固定的，時間複雜度為 O(1)，空間複雜度也為 O(1)。

參考程式碼

const actionA string = "X"
const actionB string = "O"

func TictactoeMethod1(moves [][]int) string {

	if len(moves) < 4 {
		return "Pending"
	}

	r := [3][3]string{}

	for i := 0; i < len(moves); i++ {
		x := moves[i][0]
		y := moves[i][1]

		if i%2 == 0 {
			r[x][y] = actionA
		} else {
			r[x][y] = actionB
		}

	}

	if isAWin(r) {
		return "A"
	}

	if isBWin(r) {
		return "B"
	}

	if len(moves) < 9 {
		return "Pending"
	}

	return "Draw"

}

func isAWin(r [3][3]string) bool {

	if checkCol(r, actionA) {
		return true
	}

	if checkRow(r, actionA) {
		return true
	}

	if checkDiag(r, actionA) {
		return true
	}

	return false
}

func isBWin(r [3][3]string) bool {

	if checkCol(r, actionB) {
		return true
	}

	if checkRow(r, actionB) {
		return true
	}

	if checkDiag(r, actionB) {
		return true
	}

	return false
}

func checkCol(r [3][3]string, s string) bool {

	for i := 0; i < 3; i++ {
		if r[i][0] == s && r[i][1] == s && r[i][2] == s {
			return true
		}
	}

	return false
}

func checkRow(r [3][3]string, s string) bool {

	for j := 0; j < 3; j++ {
		if r[0][j] == s && r[1][j] == s && r[2][j] == s {
			return true
		}
	}

	return false
}

func checkDiag(r [3][3]string, s string) bool {

	if r[0][0] == s && r[1][1] == s && r[2][2] == s {
		return true
	}

	if r[0][2] == s && r[1][1] == s && r[2][0] == s {
		return true
	}

	return false
}

小結:

此題讓我們熟悉對 Go 二元陣列的操作。除了方法 1 以外，網路尚有許多分享解法，如 bit operation 法以及 連線數判定法，我將各解法加上簡單的測試，上傳程式碼到此。