資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：找出網格中需要阻塞的單元格數量以建立路徑
假設有一個維度為h * w的網格。有一個機器人位於單元格位置(0, 0)，它需要到達位置(h - 1, w - 1)。網格中有兩種型別的單元格：阻塞的和未阻塞的。機器人可以穿過未阻塞的單元格，但不能穿過阻塞的單元格。機器人可以向四個方向移動：左、右、上、下。但機器人可以從一個單元格移動到另一個單元格的任何方向（忽略它之前所在的單元格），因此我們只需要建立一條路徑並阻塞該路徑之外的所有其他單元格。我們必須找出並返回為了從(0, 0)到(h - 1, w - 1)為機器人建立一條路徑，我們需要阻塞多少個單元格，如果不存在可能的路徑，則返回-1。
因此，如果輸入像h = 4，w = 4，grid = {"..#.", "#.#.", "#.##", "#..."}，則輸出將為2。
我們只需要阻塞兩個單元格即可從(0, 0)到(3, 3)建立一條路徑。
為了解決這個問題，我們將遵循以下步驟：
Define one 2D array dp
dp[0, 0] := 0
Define an array moves containing pairs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
Define one queue q
insert pair (0, 0) at the end of q
while (not q is empty), do:
p := first element of q
delete first element from q
for initialize i := 0, when i < 4, update (increase i by 1), do:
row := first value of p + first value of moves[i]
col := second value of p + second value of moves[i]
if row < 0 or row > h - 1 or col < 0 or col > w - 1, then:
Ignore following part, skip to the next iteration
if grid[row, col] is same as '#', then:
Ignore following part, skip to the next iteration
if dp[first value of p, second value of p] + 1 < dp[row, col], then:
dp[row, col] := dp[first value of p, second value of p] + 1
insert pair(row, col) into q
if dp[h - 1, w - 1] is same as 2500, then:
return -1
count := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
for initialize j := 0, when j < w, update (increase j by 1), do:
if grid[i, j] is same as '.', then:
(increase count by 1)
return count - (dp[h - 1, w - 1] + 1)示例
讓我們檢視以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(int h, int w, vector<string> grid){
vector<vector<int>> dp(h, vector<int>(w, 2500));
dp[0][0] = 0;
vector<pair<int, int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
queue<pair<int, int>> q;
q.push(make_pair(0, 0));
while (!q.empty()) {
auto p = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int row = p.first + moves[i].first;
int col = p.second + moves[i].second;
if (row < 0 || row > h - 1 || col < 0 || col > w - 1) continue;
if (grid[row][col] == '#')
continue;
if (dp[p.first][p.second] + 1 < dp[row][col]) {
dp[row][col] = dp[p.first][p.second] + 1; q.push(make_pair(row, col));
}
}
}
if (dp[h - 1][w - 1] == 2500) {
return -1;
}
int count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (grid[i][j] == '.') count++;
}
}
return count - (dp[h - 1][w - 1] + 1);
}
int main() {
int h = 4, w = 4;
vector<string> grid = {"..#.", "#.#.", "#.##", "#..."};
cout<< solve(h, w, grid);
return 0;
}輸入
4, 4, {"..#.", "#.#.", "#.##", "#..."}
輸出
2
更新於: 2022年3月2日
348 次檢視
廣告