Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/01/24 18:38)推噓3(3推 0噓 1→)

留言4則, 3人參與討論串206/719 (看更多)

909. Snakes and Ladders 給你一個board[][]矩陣表示一個棋盤，蛇梯棋是一個遊戲他有著以下規則： 1.每次投一個骰子並且走1~6步，只能往編號更高的地方走不能回頭 2.若該格子碰到蛇，一定要往前退到某一格 3.若該格子碰到梯子，一定要往上到某一格 4.起點在棋盤的左下，終點在棋盤的左上，棋盤的編號為Z字型排列假定我們的骰子可以自由的決定走1~6其中的任意步數，求出我們最少要投幾次骰子才能到達終點，若無法到達終點則返回-1。註：梯子和蛇以數字表示，若該格子為-1則表示沒有蛇也沒有梯子 Exaple： https://assets.leetcode.com/uploads/2018/09/23/snakes.png

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] Output: 4 投一次骰子並走到第2格，遇到梯子爬到第15格投一次骰子並走到第17格，遇到蛇退回13格投一次骰子投一次骰子到14格，遇到梯子爬到35格投一次骰子並走到36格(終點) 思路： 1.一開始本來是想用動態規劃求解但是怎麼求狀態轉移方程都怪怪的，只能改用DFS 或BFS這方面想，因為是求最短路徑所以一定是用BFS最好。 2.BFS的選擇可以是骰子投1~6，把下一個square的座標丟回queue裡面，並且每一輪結束的時候 move + 1。 3.有兩個點需要特別處理，一是可能出現迴圈(六個格子都是蛇)所以我們需要用一個 visited來排除掉已經走過的點，若已經走過就不繼續丟回queue。 4.第二個比較麻煩的是square的編號需要和board對應（z字型）所以每次察看棋盤前都要先把當前座標做一次轉換。 5.若超出格子的時候break，若當前點等於終點的座標則提前返回（因為是BFS所以遇到的第一個解必定是最短路徑） Java Code： ------------------------------------------------------ class Solution { public int snakesAndLadders(int[][] board) { int n = board.length; int target = n * n; Queue<Integer> queue = new LinkedList<>(); queue.add(1); boolean[] visited = new boolean[target]; visited[0] = true; int moves = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int current = queue.poll(); for (int next = current + 1; next <= current + 6; next++) { if (next > target) break; int nextSquare = getSquare(board, next); int num = nextSquare == -1 ? next : nextSquare; if (num == target) { return moves; } if (!visited[num - 1]) { queue.offer(num); visited[num - 1] = true; } } } moves++; } return -1; } private int getSquare(int[][] board, int val) { int n = board.length; int r = n - (val - 1)/n - 1; int c = (n - r) % 2 == 0 ? n - (val - 1)%n - 1 : (val - 1) % n; return board[r][c]; } } ------------------------------------------------------ 這題就三個字超級麻煩= = -- https://i.imgur.com/fHpKflu.jpg