久久久一区二区三区四区,日本女人毛片全网推荐免费看,午夜操,日本一区视频在线,日本黄视频在线观看网,熟女少妇内射日韩亚洲,蜜桃媒AV成人片免费看,成人黄A片免费

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問(wèn)題叫做?迷宮III，我們先來(lái)看題面：

https://leetcode-cn.com/problems/the-maze-iii/

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up (u), down (d), left (l) or right ?, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction. There is also a hole in this maze. The ball will drop into the hole if it rolls on to the hole.

Given the ball position, the hole position and the maze, find out how the ball could drop into the hole by moving the shortest distance. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the hole (included). Output the moving directions by using ‘u’, ‘d’, ‘l’ and ‘r’. Since there could be several different shortest ways, you should output the lexicographically smallest way. If the ball cannot reach the hole, output “impossible”.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The ball and the hole coordinates are represented by row and column indexes.

由空地和墻組成的迷宮中有一個(gè)球。球可以向上（u）下（d）左（l）右（r）四個(gè)方向滾動(dòng)，但在遇到墻壁前不會(huì)停止?jié)L動(dòng)。當(dāng)球停下時(shí)，可以選擇下一個(gè)方向。迷宮中還有一個(gè)洞，當(dāng)球運(yùn)動(dòng)經(jīng)過(guò)洞時(shí)，就會(huì)掉進(jìn)洞里。

給定球的起始位置，目的地和迷宮，找出讓球以最短距離掉進(jìn)洞里的路徑。距離的定義是球從起始位置（不包括）到目的地（包括）經(jīng)過(guò)的空地個(gè)數(shù)。通過(guò)'u', 'd', 'l' 和 'r'輸出球的移動(dòng)方向。由于可能有多條最短路徑，請(qǐng)輸出字典序最小的路徑。如果球無(wú)法進(jìn)入洞，輸出"impossible"。

迷宮由一個(gè)0和1的二維數(shù)組表示。1表示墻壁，0表示空地。你可以假定迷宮的邊緣都是墻壁。起始位置和目的地的坐標(biāo)通過(guò)行號(hào)和列號(hào)給出。

示例? ? ? ? ? ? ? ? ? ? ? ? ?

解題

https://www.cnblogs.com/grandyang/p/6746528.html

這道題在之前的兩道The Maze II和The Maze的基礎(chǔ)上又做了些改變，在路徑中間放了個(gè)陷阱，讓球在最小步數(shù)內(nèi)滾到陷阱之中，此時(shí)返回的并不是最小步數(shù)，而是滾動(dòng)的方向，用u, r, d, l 這四個(gè)字母來(lái)分別表示上右下左，而且在步數(shù)相等的情況下，讓我們返回按字母排序小的答案。相對(duì)于迷宮二那題來(lái)說(shuō)，難度是增加了一些，但我們還是可以借鑒之前那道題的思路，我們還是需要用一個(gè)二位數(shù)組dists，其中dists[i][j]表示到達(dá)(i,j)這個(gè)位置時(shí)需要的最小步數(shù)，我們都初始化為整型最大值，在后在遍歷的過(guò)程中不斷用較小值來(lái)更新每個(gè)位置的步數(shù)值。我們還需要用一個(gè)哈希表來(lái)建立每個(gè)位置跟滾到該位置的方向字符串之間的映射，這里我們用一個(gè)trick，將二維坐標(biāo)轉(zhuǎn)(i,j)為一個(gè)數(shù)字i*n+j，這實(shí)際上就是把二維數(shù)組拉成一維數(shù)組的操作，matlab中很常見(jiàn)的操作。還有需要注意的是，一滾到底的操作需要稍作修改，之前我們都是一直滾到墻里面或者界外才停止，然后做退一步處理，就是小球能滾到的位置，這里我們滾的時(shí)候要判斷陷阱，如果滾到了陷阱，那么我們也停下來(lái)，注意這時(shí)候不需要做后退一步處理。然后我們還是比較當(dāng)前步數(shù)是否小于dists中的原有步數(shù)，小于的話就更新dists，然后更新哈希表中的映射方向字符串，然后對(duì)于不是陷阱的點(diǎn)，我們加入隊(duì)列queue中繼續(xù)滾。另一點(diǎn)跟迷宮二不同的之處在于，這里還要處理另一種情況，就是當(dāng)最小步數(shù)相等的時(shí)候，并且新的滾法的方向字符串的字母順序要小于原有的字符串的時(shí)候，我們也需要更新哈希表的映射，并且判斷是否需要加入隊(duì)列queue中，參見(jiàn)代碼如下：

class?Solution?{
public:
????string?findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole)?{
????????int?m = maze.size(), n = maze[0].size();
????????vector<vector<int>> dists(m, vector<int>(n, INT_MAX));
????????vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
????????vector<char> way{'l','u','r','d'};
????????queueint, int>> q;
????????unordered_map<int, string> u;
????????dists[ball[0]][ball[1]] = 0;
????????q.push({ball[0], ball[1]});
????????while?(!q.empty()) {
????????????auto?t = q.front(); q.pop();
????????????for?(int?i = 0; i < 4; ++i) {
????????????????int?x = t.first, y = t.second, dist = dists[x][y];
????????????????string?path = u[x * n + y];
????????????????while?(x >= 0?&& x < m && y >= 0?&& y < n && maze[x][y] == 0?&& (x != hole[0] || y != hole[1])) {
????????????????????x += dirs[i][0]; y += dirs[i][1]; ++dist;
????????????????}
????????????????if?(x != hole[0] || y != hole[1]) {
????????????????????x -= dirs[i][0]; y -= dirs[i][1]; --dist;
????????????????}
????????????????path.push_back(way[i]);
????????????????if?(dists[x][y] > dist) {
????????????????????dists[x][y] = dist;
????????????????????u[x * n + y] = path;
????????????????????if?(x != hole[0] || y != hole[1]) q.push({x, y});
????????????????} else?if?(dists[x][y] == dist && u[x * n + y].compare(path) > 0) {
????????????????????u[x * n + y] = path;
????????????????????if?(x != hole[0] || y != hole[1]) q.push({x, y});
????????????????}
????????????}
????????}
????????string?res = u[hole[0] * n + hole[1]];
????????return?res.empty() ? "impossible"?: res;
????}
};