前往
大廳
主題

LeetCode - 1958. Check if Move is Legal 解題心得

Not In My Back Yard | 2022-01-09 00:00:01 | 巴幣 2 | 人氣 187

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的 8 × 8 網格 board,其中 board[r][c] 代表著遊戲版面上的格子 (r, c)。在版面上,自由格表為 '.',白格子表為 'W',而黑格子表為 'B'。

此遊戲的每步由選擇一個自由格並將其變換成你所扮演的顏色(白或黑)所組成。不過,一步是合法的若且唯若在將自由格變色後,該格將成為一個好線段(水平、鉛直或是對角線方向的)之端點。

一條好線段為一條有著三個或更多格子(包含端點)的線段,其中線段的兩端點同色,而中間的其餘格子則皆為相反的顏色(線段中沒有格子是自由的)。你可以從下圖參見一些好線段之範例:

給定兩整數 rMove 和 cMove 以及一字元表示著你當前扮演的顏色 color(白或黑),回傳真(True)如果改變格子 (rMove, cMove) 為顏色 color 為合法的一步;反之不合法則回傳假(False)。

限制:
board.length == board[r].length == 8
0 ≦ rMove 、 cMove < 8
board[rMove][cMove] == '.'
color 只會是 'B' 或 'W'。



範例測資:
範例 1:
輸入: board = [[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],["W","B","B",".","W","W","W","B"],[".",".",".","B",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."]], rMove = 4, cMove = 3, color = "B"
輸出: true
解釋: '.' 、 'W' 和 'B' 依序表為藍色、白色以及黑色,而格子 (rMove, cMove) 以一個 'X' 標記。
將選定格子作為一個端點的兩條好線段以紅色矩形標註。

範例 2:
輸入: board = [[".",".",".",".",".",".",".","."],[".","B",".",".","W",".",".","."],[".",".","W",".",".",".",".","."],[".",".",".","W","B",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".","B","W",".","."],[".",".",".",".",".",".","W","."],[".",".",".",".",".",".",".","B"]], rMove = 4, cMove = 4, color = "W"
輸出: false
解釋: 儘管有好線段將選定的格子作為中間格子,但是沒有好線段是將選定之格子作為端點的。


解題思維:
直接從 (rMove, cMove) 開始向四個方向延伸看看即可。對於某方向而言,我們就是一直延伸。如果碰到自由格或是即將超出 board 之範圍,則停在前一格;如果是碰到與 color 顏色相同的格子則停在該格。

如果有方向可以得出長度 ≧ 3(記得,這包含著起始和結束位置,即端點)且結束於 color (也就是停在顏色是 color 的格子)的線段則代表我們找到了一個好線段,因此回傳真;反之如果每個方向都找不到好線段,則回傳假。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作