前往
大廳
主題

LeetCode - 2596. Check Knight Tour Configuration 解題心得

Not In My Back Yard | 2024-02-22 12:00:06 | 巴幣 0 | 人氣 56

題目連結:


題目意譯:
現在有一個騎士在一個大小為 n × n 的棋盤。在一個合法的設置下,該騎士可以從棋盤上最左上角的格子開始並走過棋盤上每一格恰好一次。

你被給定一個大小為 n × n 的整數矩陣 grid,其由位於範圍 [0, n × n - 1] 中的相異整數所組成,其中 grid[row][col] 代表著騎士在第 grid[row][col] 步走到格子 (row, col) 上。這些步數索引值從 0 開始。

如果 grid 代表著一個騎士移動的合法設置,則回傳真(True);反之,則回傳假(False)。

注意到一個騎士的合法移動由往垂直方向移動兩格加上往水平方向移動一格或是往垂直方向移動一格加上往水平方向移動兩格所組成。下圖顯示了騎士從某個格子的所有可能移動方式。

限制:
n == grid.length == grid[i].length
3 ≦ n ≦ 7
0 ≦ grid[row][col] < n × n
grid 中所有整數相異。



範例測資:
範例 1:
輸入: grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
輸出: true
解釋: 上圖代表著 grid。可以看到其為一個合法設置。

範例 2:
輸入: grid = [[0,3,6],[5,8,1],[2,7,4]]
輸出: false
解釋: 上圖代表著 grid。考慮到騎士第 7 步的位置,第 8 步是不合法的。


解題思維:
先掃過一次 grid,把步數與它們各自的座標連結在一起存成一個陣列(因為你要判斷現在這一步相對上一步是否合法)。

然後再掃過一次這個新的陣列,來判斷每一步之間的移動是否合法即可(即判斷現在這一步與上一步的行數和列數差值是否其中一個為 2、另一個為 1)。

然後別忘記檢查第 0 步是不是在 (0, 0) 這個格子上(因為根據合法設置的定義,第一步應開始於 (0, 0))。而如果條件都通過,則回傳真;反之,則回傳假。




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

創作回應

相關創作

更多創作