摘要:題目鏈接一般這種題,給一個起點,給一個終點,最后要求最短的路徑,都是用來解。的圖不是很大,也能。
The Maze II
題目鏈接:https://leetcode.com/contest/...
一般這種題,給一個起點,給一個終點,最后要求最短的路徑,都是用bfs來解。
public class Solution { public String findShortestWay(int[][] maze, int[] ball, int[] hole) { /* minheap: check the path with smaller length first * path[x][y]: record path from ball to (x, y) * visited[x][y]: length from ball to (x, y) */ PriorityQueueheap = new PriorityQueue<>(new Comparator () { public int compare(Node a, Node b) { return a.len - b.len; } }); heap.offer(new Node(ball[0], ball[1], 1)); col = maze[0].length; // track result String result = ""; int len = Integer.MAX_VALUE; // length and path so far visited = new int[maze.length][maze[0].length]; visited[ball[0]][ball[1]] = 1; path = new String[maze.length][maze[0].length]; path[ball[0]][ball[1]] = ""; while(!heap.isEmpty()) { Node cur = heap.poll(); visited[cur.x][cur.y] = cur.len; // find the hole, update result if(cur.x == hole[0] && cur.y == hole[1]) { if(len > cur.len || (len == cur.len && result.compareTo(path[cur.x][cur.y]) > 0)) { len = cur.len; result = path[cur.x][cur.y]; } continue; } // 4 directions for(int i = 0; i < 4; i++) { int nx = cur.x, ny = cur.y; int depth = cur.len; // find the next position (reach before the wall) while(nx + dx[i] >= 0 && nx + dx[i] < maze.length && ny + dy[i] >= 0 && ny + dy[i] < maze[0].length) { // find the path so far from ball to [nx, ny] String curPath = path[cur.x][cur.y] + (nx == cur.x && ny == cur.y ? "" : dir[i]); // reach the hole if(nx == hole[0] && ny == hole[1]) break; // meet the wall if(maze[nx + dx[i]][ny + dy[i]] == 1) break; // loop update depth++; nx += dx[i]; ny += dy[i]; } // pruning if(depth > len) continue; String curPath = path[cur.x][cur.y] + (nx == cur.x && ny == cur.y ? "" : dir[i]); if(visited[nx][ny] != 0 && visited[nx][ny] < depth) continue; if(visited[nx][ny] != 0 && visited[nx][ny] == depth && path[nx][ny].compareTo(curPath) <= 0) continue; // add new path visited[nx][ny] = depth; path[nx][ny] = curPath; heap.offer(new Node(nx, ny, depth)); } } return result.length() == 0 ? "impossible" : result; } int[] dx = new int[] {1, 0, 0, -1}; int[] dy = new int[] {0, -1, 1, 0}; char[] dir = new char[] {"d", "l", "r", "u"}; int[][] visited; String[][] path; int col; class Node { int x, y; int len; Node(int x, int y, int len) { this.x = x; this.y = y; this.len = len; } @Override public int hashCode() { return this.x * col + this.y; } @Override public boolean equals(Object a) { if(a instaceof Node) { Node b = (Node) a; return b.x == this.x && b.y == this.y; } return false; } } }
test的圖不是很大,dfs也能ac。
public class Solution { public String findShortestWay(int[][] maze, int[] ball, int[] hole) { /* use global variable: result and len */ visited = new boolean[maze.length][maze[0].length]; dfs(maze, ball[0], ball[1], hole, 1, ""); return result.length() == 0 ? "impossible" : result; } String result = ""; int len = Integer.MAX_VALUE; boolean[][] visited; int[] dx = new int[] {1, 0, 0, -1}; int[] dy = new int[] {0, -1, 1, 0}; char[] dir = new char[] {"d", "l", "r", "u"}; // dfs private void dfs(int[][] maze, int x, int y, int[] hole, int dep, String path) { if(dep > len) return; if(x == hole[0] && y == hole[1]) { if(len > dep) { len = dep; result = path; } if(len == dep && path.compareTo(result) < 0) { len = dep; result = path; } return; } if(visited[x][y]) return; visited[x][y] = true; // 4 directions for(int i = 0; i < 4; i++) { int nx = x, ny = y; while(nx + dx[i] >= 0 && nx + dx[i] < maze.length && ny + dy[i] >= 0 && ny + dy[i] < maze[0].length) { // meet the wall if(maze[nx + dx[i]][ny + dy[i]] == 1) break; nx += dx[i]; ny += dy[i]; if(visited[nx][ny]) break; if(nx == hole[0] && ny == hole[1]) break; } if(!visited[nx][ny]) dfs(maze, nx, ny, hole, dep + Math.abs(nx - x) + Math.abs(ny - y), path + dir[i]); } visited[x][y] = false; } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66557.html
摘要:題目鏈接和上一題不一樣的是這道題要求最短的路徑,普通的遍歷和都是可以做的,但是求最短路徑的話還是用。這里相當于每個點有至多條相連,每條的就是到墻之前的長度。 490. The Maze 題目鏈接:https://leetcode.com/problems... 又是圖的遍歷問題,就是簡單的遍歷,所以dfs和bfs都可以做,復(fù)雜度也是一樣的。這道題要求球不能停下來,即使碰到destina...
Problem There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it wont stop rolling until hitting a wall. When the ball sto...
摘要:實驗蒙特祖瑪?shù)膹?fù)仇蒙特祖瑪?shù)膹?fù)仇是上最難的游戲之一。圖蒙特祖瑪?shù)膹?fù)仇的學(xué)習曲線在第一個房間中學(xué)習的子目標的可視化呈現(xiàn)。結(jié)論如何創(chuàng)建一個能夠?qū)W習將其行為分解為有意義的基元,然后重新利用它們以更有效地獲取新的行為,這是一個長期存在的研究問題。 論文題目:分層強化學(xué)習的 FeUdal 網(wǎng)絡(luò)(FeUdal Networks for Hierarchical Reinforcement Learnin...
摘要:整個思路十分簡單首先我們將迷宮視為一個行列的單元格組合,每一個單元格便可以表示為。用來儲存我們已訪問過的單元格,則記錄我們的訪問路徑。我們通過將單元格的,,,屬性設(shè)置為或來標識這個方向是否應(yīng)該有邊框,同時該方向是否可走。 這個系列分為兩部分,第一部分為迷宮的生成及操作,第二部分為自動尋路算法。 我們先看效果:點擊查看 我們直入正題,先說一說生成迷宮的思路。 整個思路十分簡單: 首先...
閱讀 3186·2021-11-24 09:39
閱讀 2923·2021-11-23 09:51
閱讀 887·2021-11-18 10:07
閱讀 3544·2021-10-11 10:57
閱讀 2740·2021-10-08 10:04
閱讀 2999·2021-09-26 10:11
閱讀 1046·2021-09-23 11:21
閱讀 2780·2019-08-29 17:28