資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式找出網格中從一個未阻塞單元格到另一個未阻塞單元格的最大移動次數
假設，我們給定一個維度為h * w的網格，其中包含兩種型別的單元格，阻塞的和未阻塞的。阻塞的單元格表示該單元格不可訪問，未阻塞的表示該單元格可訪問。我們用一個二維陣列表示網格，其中阻塞的單元格用“#”表示，未阻塞的單元格用“.”表示。現在，我們必須從網格中的一個未阻塞單元格到達另一個未阻塞單元格。我們只能執行兩種移動，我們可以垂直移動或水平移動。我們不能對角移動。我們必須記住，我們只能移動到未阻塞的單元格。因此，我們必須找出在網格中從一個未阻塞單元格到達另一個未阻塞單元格所需的最大移動次數。
因此，如果輸入類似於h = 4，w = 4，grid = {"..#.", "#.#.", "..##", "###."}，則輸出將為4。
從單元格(0,0)開始，到達單元格(2, 0)最多需要4次移動。
為了解決這個問題，我們將遵循以下步驟 -
Define an array xdir of size: 4 := {1, 0, - 1, 0}
Define an array ydir of size: 4 := {0, 1, 0, - 1}
Define one 2D array dist
Define one 2D array reset
res := 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:
dist := reset
if grid[i, j] is same as '.', then:
dist[i, j] := 0
Define one queue q containing integer pairs
insert make_pair(i, j) into q
while (not q is empty), do:
x := first element of the leftmost element in the q
y := second element of the leftmost element in the q
res := maximum of (dist[x, y] and res)
delete leftmost element from q
for initialize k := 0, when k < 4, update (increase k by 1), do:
px := x + xdir[k]
py := y + ydir[k]
if px >= 0 and px < h and py >= 0 and py < w, then:
if grid[px, py] is same as '.', then:
if dist[px, py] is same as -1, then:
dist[px, py] := dist[x, y] + 1
insert pair(px, py) into q
return res示例
讓我們看看以下實現以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
int solve(int h, int w, vector<string> grid){
int xdir[4] = {1, 0, -1, 0};
int ydir[4] = {0, 1, 0, -1};
vector<vector<int>> dist(h, vector<int>(w, -1));
vector<vector<int>> reset(h, vector<int>(w, -1));
int res = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
dist = reset;
if(grid[i][j] == '.'){
dist[i][j] = 0;
queue<pair<int,int>> q;
q.push(make_pair(i, j));
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
res = max(dist[x][y], res);
q.pop();
for(int k = 0; k < 4; k++){
int px = x + xdir[k];
int py = y + ydir[k];
if(px >= 0 && px < h && py >= 0 && py < w){
if(grid[px][py] == '.'){
if(dist[px][py] == -1){
dist[px][py] = dist[x][y] + 1; q.push(make_pair(px, py));
}
}
}
}
}
}
}
}
return res;
}
int main() {
int h = 4, w = 4;
vector<string> grid = {"..#.", "#.#.", "..##", "###."};
cout << solve(h, w, grid);
return 0;
}輸入
4, 4, {"..#.", "#.#.", "..##", "###."}
輸出
4
更新於: 2022年3月2日
258 次瀏覽
廣告