隨想錄 Day 74 Floyd / A*

Bellman_ford 隊列優化

97. 小明逛公園

時間限制：1.000S 空間限制：256MB
題目描述
小明喜歡去公園散步，公園內布置了許多的景點，相互之間通過小路連接，小明希望在觀看景點的同時，能夠節省體力，走最短的路徑。

給定一個公園景點圖，圖中有 N 個景點（編號為 1 到 N），以及 M 條雙向道路連接著這些景點。每條道路上行走的距離都是已知的。

小明有 Q 個觀景計劃，每個計劃都有一個起點 start 和一個終點 end，表示他想從景點 start 前往景點 end。由于小明希望節省體力，他想知道每個觀景計劃中從起點到終點的最短路徑長度。 請你幫助小明計算出每個觀景計劃的最短路徑長度。

輸入描述
第一行包含兩個整數 N, M, 分別表示景點的數量和道路的數量。

接下來的 M 行，每行包含三個整數 u, v, w，表示景點 u 和景點 v 之間有一條長度為 w 的雙向道路。

接下里的一行包含一個整數 Q，表示觀景計劃的數量。

接下來的 Q 行，每行包含兩個整數 start, end，表示一個觀景計劃的起點和終點。

輸出描述
對于每個觀景計劃，輸出一行表示從起點到終點的最短路徑長度。如果兩個景點之間不存在路徑，則輸出 -1。
輸入示例
7 3
2 3 4
3 6 6
4 7 8
2
2 3
3 4
輸出示例
4
-1

提交

1、確定dp數組（dp table）以及下標的含義

這里我們用 grid數組來存圖，那就把dp數組命名為 grid。

grid[i][j][k] = m，表示 節點i 到 節點j 以[1…k] 集合為中間節點的最短距離為m。

# include <iostream>
# include <vector>
using namespace std;
int n, m;
int cnt;
int main() {cin>> n >>m;vector<vector<vector<int> > >  grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005))); for (int c = 0; c < m; c++) {int i, j , weight;cin>> i >>j >> weight;//cout << i << j << weight<<endl;grid[i][j][0] = weight;//注意這里是雙向圖grid[j][i][0] = weight;}for (int k = 1 ; k < n+1; k++) {for (int i = 1; i < n+1; i++) {for (int j = 1; j < n+1; j++){grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);}}}cin>> cnt;for (int i = 0; i < cnt; i++) {int start, end;cin>> start >> end;if (grid[start][end][n] > 10000){cout<< -1<< endl;} else {cout<< grid[start][end][n]<<endl;}}
}

A* method

原理介紹

題目：
126. 騎士的攻擊

時間限制：1.000S 空間限制：256MB
題目描述
在象棋中，馬和象的移動規則分別是“馬走日”和“象走田”。現給定騎士的起始坐標和目標坐標，要求根據騎士的移動規則，計算從起點到達目標點所需的最短步數。

棋盤大小 1000 x 1000（棋盤的 x 和 y 坐標均在 [1, 1000] 區間內，包含邊界）

輸入描述
第一行包含一個整數 n，表示測試用例的數量，1 <= n <= 100。

接下來的 n 行，每行包含四個整數 a1, a2, b1, b2，分別表示騎士的起始位置 (a1, a2) 和目標位置 (b1, b2)。

輸出描述
輸出共 n 行，每行輸出一個整數，表示騎士從起點到目標點的最短路徑長度。
輸入示例
6
5 2 5 4
1 1 2 2
1 1 8 8
1 1 8 7
2 1 3 3
4 6 4 6
輸出示例
2
4
6
5
1
0

提交

注意幾個細節

memst 再string.h包中

注意huristicbic 必須帶const 因為會被operator調用

A* 算法中沒走一步要* 5 (1^2 + 2^2)

pq.push(vector{x, y}); 注意這里的語法，容易寫成小括號，還不好查錯誤。

# include <iostream>
# include <vector>
# include <queue>
# include<string.h>
using namespace std;
int n;
int moves[1001][1001];
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
vector<int> start(2);
vector<int> target(2);
int Heuristic(const vector<int>& a, const vector<int>&b)  { // 歐拉距離return (a[1] - b[1]) * (a[1] - b[1]) + (a[0] - b[0]) * (a[0] - b[0]); // 統一不開根號，這樣可以提高精度
};
class cmp {public:bool operator() (const vector<int>& a, const vector<int>&b) {return moves[a[0]][a[1]] * 5 + Heuristic(a, target) > moves[b[0]][b[1]] * 5 + Heuristic(b, target);}
};
int shortestPath() {if (start == target) return 0;priority_queue<vector<int>, vector<vector<int> >, cmp > pq;//<vector<int> > q;//q.push(start);pq.push(start);//cout<< start[0] << "  " <<start[1] <<  endl;while(pq.size() != 0) {vector<int> now = pq.top();pq.pop();//cout << "now[0] " << now[0] << "  now[1] " <<now[1] <<"  move[now[0]][now[1]]  "<<moves[now[0]][now[1]] <<endl;for (int idx = 0; idx < 8; idx++) {int x = now[0] + dir[idx][0];int y = now[1] + dir[idx][1];//cout << "now[0] " << now[0] << "now[1] " <<now[1] <<"move[now[0]][now[1]]  "<<moves[now[0]][now[1]] <<endl;if (x == target[0] && y == target[1]) {return moves[now[0]][now[1]] + 1;}if (x >= 1 && x <= 1000 && y >= 1 && y <= 1000) {if (moves[x][y] == 0) {moves[x][y] = moves[now[0]][now[1]] + 1;pq.push(vector<int>{x, y});//cout << " x "<<x << " y "<< y <<" moves[x][y]" << moves[x][y]<<  endl;}}}}return -1;
};
int main() {cin>> n;for(int t = 0; t < n; t ++) {memset(moves,0,sizeof(moves));cin>> start[0] >> start[1]>> target[0] >> target[1];//cout << start[0] << " " << start[1]<< " " << target[0]<< " "<< target[1] << endl;cout << shortestPath()<<endl;}
}

A* 補充題

https://leetcode.cn/problems/shortest-path-in-binary-matrix/

1091. 二進制矩陣中的最短路徑

提示
中等
給你一個 n x n 的二進制矩陣 grid 中，返回矩陣中最短 暢通路徑 的長度。如果不存在這樣的路徑，返回 -1 。
二進制矩陣中的 暢通路徑 是一條從 左上角 單元格（即，(0, 0)）到 右下角 單元格（即，(n - 1, n - 1)）的路徑，該路徑同時滿足下述要求：
路徑途經的所有單元格的值都是 0 。
路徑中所有相鄰的單元格應當在 8 個方向之一 上連通（即，相鄰兩單元之間彼此不同且共享一條邊或者一個角）。
暢通路徑的長度 是該路徑途經的單元格總數。

Odinary bfs method

比較難看并不推薦

class Solution {
public:int dirs[8][2] = {{-1, 1}, {0, 1}, {1, 1},{-1, 0},         {1, 0},{-1, -1},{0, -1}, {1, -1}};int shortestPathBinaryMatrix(vector<vector<int>>& grid) {queue<pair<int,int> > que;int n = grid.size(); if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;if ( n == 1 ) return 1;que.emplace(0, 0);grid[0][0] = 1;int res = 1;while(!que.empty()) {res ++;int size = que.size();while (size--) {pair<int, int> temp = que.front();que.pop();for (int i = 0; i < 8; i++) {int x = temp.first + dirs[i][0];int y = temp.second + dirs[i][1];if (x == n-1 && y == n-1) return res;if (x >= 0 && x < n && y >= 0 && y < n) {if (grid[x][y] == 0) {que.emplace(x, y);grid[x][y] = 1;}}}}}return -1;}                                                                                                                                      
};

bfs with class method

class Solution {
public:int dirs[8][2] = {{-1, 1}, {0, 1}, {1, 1},{-1, 0},         {1, 0},{-1, -1}, {0, -1}, {1, -1}};class Node{public:int x, y, dis;Node(int a, int b, int c = 0) {x = a;y = b;dis = c;}};int shortestPathBinaryMatrix(vector<vector<int>>& grid) {queue<Node> que;int n = grid.size();if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;if (n == 1) return 1;Node start(0, 0, 1);que.push(start);grid[0][0] = 1;while (!que.empty()) {Node nod = que.front();que.pop();for (int i = 0; i < 8; i++) {int dx = nod.x + dirs[i][0];int dy = nod.y + dirs[i][1];int disten = nod.dis + 1;if (dx == n-1 && dy == n-1) {return disten;}if (dx < n && dx >= 0 && dy < n && dy >= 0 && grid[dx][dy] == 0) {grid[dx][dy] = 1;Node temp(dx, dy, disten);que.push(temp);}}}return -1;}
};

A* method

class Solution {
public:int dirs[8][2] = {{-1, 1}, {0, 1}, {1, 1},{-1, 0},         {1, 0},{-1, -1}, {0, -1}, {1, -1}};class Node{public:int x, y, dis, h;Node(int a, int b, int c) {x = a;y = b;dis = c;h = c + max(-a, -b);//針對切比雪夫距離的優化}friend bool operator <(Node f1, Node f2) {return f1.h > f2.h;}};   int shortestPathBinaryMatrix(vector<vector<int>>& grid) {int n = grid.size();priority_queue<Node> que;vector<vector<int> > minmap(n, vector<int>(n, 10000));
//記錄當前最小if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;if (n == 1) return 1;Node start(0, 0, 1);que.push(start);//grid[0][0] = 1;minmap[0][0] = start.h;while (!que.empty()) {Node nod = que.top();que.pop();for (int i = 0; i < 8; i++) {int dx = nod.x + dirs[i][0];int dy = nod.y + dirs[i][1];int disten = nod.dis + 1;if (dx == n-1 && dy == n-1) {return disten;}if (dx < n && dx >= 0 && dy < n && dy >= 0 && grid[dx][dy] == 0) {Node temp(dx, dy, disten); if( minmap[dx][dy] > temp.h){minmap[dx][dy] = temp.h;que.push(temp);}}}}return -1;}
};

sliding-puzzle

https://leetcode.cn/problems/sliding-puzzle/

在一個 2 x 3 的板上（board）有 5 塊磚瓦，用數字 1~5 來表示, 以及一塊空缺用 0 來表示。一次 移動 定義為選擇 0 與一個相鄰的數字（上下左右）進行交換.
最終當板 board 的結果是 [[1,2,3],[4,5,0]] 謎板被解開。
給出一個謎板的初始狀態 board ，返回最少可以通過多少次移動解開謎板，如果不能解開謎板，則返回 -1 。

BFS

class Solution {
public:string boardToString (vector<vector<int>> board) {string ret = "";for(int j = 0 ; j < 2; j++) {for (int i = 0; i < 3; i++) {ret += char(board[j][i] + '0');}}return ret;};vector<vector<int>> trans = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};vector<string> nextStates(string now) {vector<string> ret;int loc = now.find('0');for (int exchangeLoc : trans[loc]) {swap(now[loc], now[exchangeLoc]);ret.push_back(now);swap(now[loc], now[exchangeLoc]);}return ret;};int slidingPuzzle(vector<vector<int>>& board) {string start = boardToString(board);if (start == "123450") return 0;unordered_set<string> reached;reached.insert(start);queue<pair<string, int> >q;q.emplace(start, 0);while(!q.empty()) {string now = q.front().first;int step = q.front().second;q.pop();step ++;for (string nxt : nextStates(now)) {if (nxt == "123450") return step;if (!reached.count(nxt)) {q.emplace(nxt, step);reached.insert(nxt);}}}return -1;}
};

A* methods

class Solution {
public:string boardToString (vector<vector<int>> board) {string ret = "";for(int j = 0 ; j < 2; j++) {for (int i = 0; i < 3; i++) {ret += char(board[j][i] + '0');}}return ret;};vector<vector<int> > trans = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};class States {public:vector<vector<int> > Manhatten = {{0, 1, 2, 1, 2, 3},{1, 0, 1, 2, 1, 2},{2, 1, 0, 3, 2, 1},{1, 2, 3, 0, 1, 2},{2, 1, 2, 1, 0, 1},{3, 2, 1, 2, 1, 0}};string state;int step;int h;int f;        States(string st, int sp) {state = st;step = sp;h = get_h(st);f = h + sp;};int get_h(string st) {int ret = 0;for (int i = 0; i <6; i++) {if (st[i] != '0') {ret += Manhatten[i][st[i] - '1'];}}return ret;};friend bool operator < (const States &a, const States &b) {return a.f > b.f;};};vector<string> nextStates(string now) {vector<string> ret;int loc = now.find('0');for (int exchangeLoc : trans[loc]) {swap(now[loc], now[exchangeLoc]);ret.push_back(now);swap(now[loc], now[exchangeLoc]);}return ret;};int slidingPuzzle(vector<vector<int>>& board) {string start = boardToString(board);if (start == "123450") return 0;States init(start, 0);unordered_map<string, int> min_reached;min_reached[init.state] = init.f;priority_queue<States>q;q.push(init);while(!q.empty()) {States current = q.top();q.pop();string now = current.state;int step = current.step;step ++;for (string nxt : nextStates(now)) {if (nxt == "123450") return step;States next(nxt, step);if (!min_reached.count(nxt) || min_reached[nxt] > next.f ) {min_reached[nxt] = next.f;q.push(next);}}}return -1;}
};