資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：計算機器人到達網格中特定單元格所需的跳躍次數
假設我們有一個h x w維度的網格。該網格用一個名為‘initGrid’的二維陣列表示，其中網格中的每個單元格都用‘#’或‘.’表示。‘#’表示網格中存在障礙物，‘.’表示該單元格可以透過。現在，一個機器人放置在網格上的單元格'c'上，該單元格的行號為x，列號為y。機器人必須移動到另一個單元格'd'，其行號為p，列號為q。單元格座標c和d都以整數對的形式提供給我們。現在，機器人可以透過以下方式從一個單元格移動到另一個單元格：
如果機器人想要移動到的單元格位於其當前所在單元格的垂直或水平相鄰位置，則機器人可以從一個單元格走到另一個單元格。
機器人可以跳到以其當前所在單元格為中心的5×5區域內的任何單元格。
只有當目標單元格不包含障礙物時，機器人才能移動到網格中的另一個單元格。機器人也不能離開網格。
我們必須找出機器人到達目的地所需的跳躍次數。
因此，如果輸入類似於h = 4，w = 4，c = {2, 1}，d = {4, 4}，initGrid = {"#...", ".##.", "...#", "..#."}，則輸出為1。機器人只需要一次跳躍即可到達目的地。
為了解決這個問題，我們將遵循以下步驟：
N:= 100
Define intger pairs s and t.
Define an array grid of size: N.
Define an array dst of size: N x N.
Define a struct node that contains integer values a, b, and e.
Define a function check(), this will take a, b,
return a >= 0 AND a < h AND b >= 0 AND b < w
Define a function bfs(), this will take a, b,
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:
dst[i, j] := infinity
dst[a, b] := 0
Define one deque doubleq
Insert a node containing values {a, b, and dst[a, b]} at the end of doubleq
while (not doubleq is empty), do:
nd := first element of doubleq
if e value of nd > dst[a value of nd, b value of nd], then:
Ignore the following part, skip to the next iteration
for initialize diffx := -2, when diffx <= 2, update (increase diffx by 1), do:
for initialize diffy := -2, when diffy <= 2, update (increase diffy by 1), do:
tm := |diffx + |diffy||
nx := a value of nd + diffx, ny = b value of nd + diffy
if check(nx, ny) and grid[nx, ny] is same as '.', then:
w := (if tm > 1, then 1, otherwise 0)
if dst[a value of nd, b value of nd] + w < dst[nx, ny], then:
dst[nx, ny] := dst[a value of nd, b value of nd] + w
if w is same as 0, then:
insert node containing values ({nx, ny, dst[nx, ny]}) at the beginning of doubleq.
Otherwise
insert node containing values ({nx, ny, dst[nx, ny]}) at the end of doubleq.
s := c
t := d
(decrease first value of s by 1)
(decrease second value of s by 1)
(decrease first value of t by 1)
(decrease second value of t by 1)
for initialize i := 0, when i < h, update (increase i by 1), do:
grid[i] := initGrid[i]
bfs(first value of s, second value of s)
print(if dst[first value of t, second value of t] is same as infinity, then -1, otherwise dst[first value of t, second value of t])示例
讓我們看看下面的實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int h, w;
pair<int, int> s, t;
string grid[N];
int dst[N][N];
struct node {
int a, b, e;
};
bool check(int a, int b) {
return a >= 0 && a < h && b >= 0 && b < w;
}
void bfs(int a, int b) {
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++)
dst[i][j] = INF;
}
dst[a][b] = 0;
deque<node> doubleq;
doubleq.push_back({a, b, dst[a][b]});
while (!doubleq.empty()) {
node nd = doubleq.front();
doubleq.pop_front();
if (nd.e > dst[nd.a][nd.b])
continue;
for (int diffx = -2; diffx <= 2; diffx++) {
for (int diffy = -2; diffy <= 2; diffy++) {
int tm = abs(diffx) + abs(diffy);
int nx = nd.a + diffx, ny = nd.b + diffy;
if (check(nx, ny) && grid[nx][ny] == '.') {
int w = (tm > 1) ? 1 : 0;
if (dst[nd.a][nd.b] + w < dst[nx][ny]) {
dst[nx][ny] = dst[nd.a][nd.b] + w;
if (w == 0)
doubleq.push_front({nx, ny, dst[nx][ny]});
else
doubleq.push_back({nx, ny, dst[nx][ny]});
}
}
}
}
}
}
void solve(pair<int,int> c, pair<int, int> d, string initGrid[]){
s = c;
t = d;
s.first--, s.second--, t.first--, t.second--;
for(int i = 0; i < h; i++)
grid[i] = initGrid[i];
bfs(s.first, s.second);
cout << (dst[t.first][t.second] == INF ? -1 :
dst[t.first][t.second]) << '\n';
}
int main() {
h = 4, w = 4;
pair<int,int> c = {2, 1}, d = {4, 4};
string initGrid[] = {"#...", ".##.", "...#", "..#."};
solve(c, d, initGrid);
return 0;
}輸入
4, 4, {2, 1}, {4, 4}, {"#...", ".##.", "...#", "..#."}輸出
1
更新於：2022年2月25日
瀏覽量：193
廣告