資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式查詢到達目標所需的最小拳擊次數
假設我們有一個包含H行和W列的矩陣。單元格中包含“.”或“#”。點“.”表示可通行空間，“#”表示障礙。Amal將從他的家到市場。他的家位於左上角的單元格，市場位於右下角的單元格。Amal可以向上、下、左或右移動一個單元格到可通行單元格。他不能離開城鎮。他也不可以進入障礙單元格。然而，他的體力允許他用一拳摧毀他選擇的2×2單元格的正方形區域中的所有障礙，使這些單元格可通行。我們必須找到Amal到達市場所需的最小拳擊次數。
因此，如果輸入類似於
| . | . | # | . | . |
| # | . | # | . | # |
| # | # | . | # | # |
| # | . | # | . | # |
| . | . | # | . | . |
那麼輸出將是1，因為我們可以將網格更改為 -
| . | . | # | . | . |
| # | . | . | . | # |
| # | # | . | . | # |
| # | . | # | . | # |
| . | . | # | . | . |
透過摧毀標記的方塊
步驟
為了解決這個問題，我們將遵循以下步驟 -
n := row count of matrix
m := column count of matrix
Define one 2D array dist of order (n + 1) x (m + 1)
Define one deque dq
insert ( 0, 0 ) at the beginning of dq
dist[0, 0] := 0
while (not dq is empty), do:
v := first element of dq
delete front element from dq
for initialize i := 0, when i < 4, update (increase i by 1), do:
x := dx[i] + v[0]
y := dy[i] + v[1]
if x >= 0 and x < n and y >= 0 and y < m, then:
if matrix[x, y] is same as '.', then:
if dist[x, y] > dist[v[0], v[1]], then:
dist[x, y] := dist[v[0], v[1]]
insert pair { x, y } at the beginning of dq
Otherwise
for initialize p := x - 1, when p <= x + 1, update (increase p by 1), do:
for initialize q := y - 1, when q <= y + 1, update (increase q by 1), do:
if p >= 0 and p < n and q >= 0 and q < m, then:
if dist[p, q] > dist[v[0], v[1]] + 1, then:
dist[p, q] := dist[v[0], v[1]] + 1
insert pair { p, q } at the end of dq
return dist[n - 1, m - 1]示例
讓我們看看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int solve(vector<vector<char>> matrix){
int n = matrix.size();
int m = matrix[0].size();
vector<vector<int>> dist(n + 1, vector<int>(m + 1, 1e9));
deque<array<int, 2>> dq;
dq.push_front({ 0, 0 });
dist[0][0] = 0;
while (!dq.empty()){
auto v = dq.front();
dq.pop_front();
for (int i = 0; i < 4; i++){
int x = dx[i] + v[0], y = dy[i] + v[1];
if (x >= 0 && x < n && y >= 0 && y < m){
if (matrix[x][y] == '.'){
if (dist[x][y] > dist[v[0]][v[1]]){
dist[x][y] = dist[v[0]][v[1]];
dq.push_front({ x, y });
}
} else{
for (int p = x - 1; p <= x + 1; p++){
for (int q = y - 1; q <= y + 1; q++){
if (p >= 0 && p < n && q >= 0 && q < m){
if (dist[p][q] > dist[v[0]][v[1]] + 1){
dist[p][q] = dist[v[0]][v[1]] + 1;
dq.push_back({ p, q });
}
}
}
}
}
}
}
}
return dist[n - 1][m - 1];
}
int main(){
vector<vector<char>> matrix = { { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' }, { '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, { '.', '.', '#', '.', '.' } };
cout << solve(matrix) << endl;
}輸入
{ { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' },
{ '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, {
'.', '.', '#', '.', '.' } }輸出
1
更新於: 2022年3月3日
245 次檢視
廣告