資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 迷宮 III
假設有一個迷宮，其中包含空的空間和牆壁，迷宮中還有一個球。球可以透過向上 (u)、向下 (d)、向左 (l) 或向右 (r) 滾動穿過空的空間，但它會一直滾動直到碰到牆壁。當球停止時，它可以選擇下一個方向。迷宮中還有一個洞。如果球滾到洞上，它就會掉進洞裡。
因此，如果我們有球的位置、洞的位置和迷宮，我們必須找出球如何透過移動最短距離掉入洞中。這裡的距離由球從起點（不包括）到洞（包括）經過的空空間的數量定義。
使用 'u'、'd'、'l' 和 'r' 返回移動方向。由於可能存在幾種不同的最短路徑，輸出應為字典序最小的路徑。如果球無法到達洞，則顯示“impossible”。
這裡迷宮由一個二進位制矩陣表示。1 表示牆壁，0 表示空空間。球和洞的座標由行和列索引表示。
所以，如果輸入像這樣
則輸出將為 'lul'，表示先向左移動，然後向上，再向左，另一個結果可能是 'ul'，先向上再向左，兩者長度均為 6，但它在字典序上不小於 'lul'
為了解決這個問題，我們將遵循以下步驟：
定義一個名為 Data 的資料型別，它將包含距離、字串 d 和座標 x、y。
定義一個大小為 4 x 2 的陣列 dir：={{1, 0}, {0, - 1}, {0, 1}, { - 1, 0}}
定義一個大小為 4 的陣列 dirst：={'d', 'l', 'r', 'u'}
定義一個函式 ok()，它將接收 x1、y1、x2、y2，
如果 x1 等於 x2 且 y1 等於 y2，則返回 true
從主方法執行以下操作：
n := 迷宮的行大小
m := （如果 n 不為零，則為迷宮的列大小，否則為 0）
定義一個優先順序佇列 pq
將新的資料 (0, ball[0], ball[1], "") 插入 pq
定義一個大小為 n x m 的二維陣列 visited
當 (pq 不為空) 時，執行以下操作：
curr := pq 的頂部元素
x := curr.x
y := curr.y
dist := curr.dist
d := curr.d
如果 ok(x, y, hole[0], hole[1])，則：
返回 d
visited[x, y] := true
從 pq 中刪除元素
從 k 初始化為 0，當 k - 4 時，更新（k 增加 1），執行以下操作：
nx := x，ny := y
tempDist := 0
當 nx + dir[k, 0] < n 且 nx + dir[k, 0] >= 0 且 ny + dir[k, 1] < m 且 ny + dir[k, 1] >= 0 且 maze[nx + dir[k, 0], ny + dir[k, 1]] 為 0 時，執行以下操作：
nx := nx + dir[k, 0]
ny := ny + dir[k, 1]
（tempDist 增加 1）
如果 ok(nx, ny, hole[0], hole[1])，則：
退出迴圈
如果 visited[nx, ny] 為零，則：
將新的 Data(dist + tempDist, nx, ny, d + dirst[k]) 插入 pq
返回“impossible”
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char dirst[4] = {'d', 'l', 'r', 'u'};
class Solution {
public:
struct Data {
int dist;
string d;
int x, y;
Data(int a, int b, int c, string s) {
d = s;
dist = a;
x = b;
y = c;
}
};
struct Comparator {
bool operator()(Data a, Data b) {
return a.dist != b.dist ? !(a.dist < b.dist) : !(a.d < b.d);
}
};
bool ok(int x1, int y1, int x2, int y2) { return x1 == x2 && y1 == y2; }
string findShortestWay(vector<vector<int>> &maze, vector<int>&ball,
vector<int> &hole) {
int n = maze.size();
int m = n ? maze[0].size() : 0;
priority_queue<vector<Data>, vector<Data>, Comparator> pq;
pq.push(Data(0, ball[0], ball[1], ""));
vector<vector<bool>> visited(n, vector<bool>(m));
while (!pq.empty()) {
Data curr = pq.top();
int x = curr.x;
int y = curr.y;
int dist = curr.dist;
string d = curr.d;
if (ok(x, y, hole[0], hole[1])) {
return d;
}
visited[x][y] = true;
pq.pop();
for (int k = 0; k < 4; k++) {
int nx = x;
int ny = y;
int tempDist = 0;
while (nx + dir[k][0] < n && nx + dir[k][0] >= 0 && ny + dir[k][1] < m && ny + dir[k][1] >= 0 && !maze[nx + dir[k][0]][ny + dir[k][1]]) {
nx += dir[k][0];
ny += dir[k][1];
tempDist++;
if (ok(nx, ny, hole[0], hole[1]))
break;
}
if (!visited[nx][ny]) {
pq.push(Data(dist + tempDist, nx, ny, d + dirst[k]));
}
}
}
return "impossible";
}
};
main() {
Solution ob;
vector<vector<int>> v = {
{0, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 0}};
vector<int> v1 = {4, 3}, v2 = {0, 1};
cout << (ob.findShortestWay(v, v1, v2));
}輸入
vector<vector<int>> v = {{0, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 0}};
vector<int> v1 = {4, 3}, v2 = {0, 1};輸出
lul
407 次瀏覽
