資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：查詢網格中從一端到另一端所需更改的次數
假設我們給定一個x * y維的網格，其中包含兩種型別的單元格：阻塞單元格和非阻塞單元格。阻塞單元格表示單元格不可訪問，非阻塞單元格表示單元格可訪問。我們用一個二維陣列表示網格，其中阻塞單元格用'#'表示，非阻塞單元格用'.'表示。現在，我們必須從單元格(0, 0)到達單元格(x, y)。我們只能執行兩種移動：可以向右移動一個單元格，或者向下移動一個單元格。我們必須記住，我們只能在非阻塞單元格中移動，並且(0, 0)和(x, y)都是非阻塞單元格。如果我們無法從(0, 0)到達(x, y)，我們可以將一個阻塞單元格更改為非阻塞單元格。我們必須找到執行到達目標所需的最少更改操作次數。
因此，如果輸入是這樣的：x = 4，y = 4，grid = {"..#.", "#.#.", "#.##", "###."}，則輸出將為1。
只需要執行一次更改操作。如果我們將單元格(2, 2)從阻塞更改為非阻塞，那麼我們就可以從(0, 0)到達(3, 3)。
步驟
為了解決這個問題，我們將遵循以下步驟：
Define one 2D array mat
if grid[0, 0] is same as '#', then:
mat[0, 0] := 1
Otherwise
mat[0, 0] := 0
for initialize i := 0, when i < x, update (increase i by 1), do:
for initialize j := 0, when j < y, update (increase j by 1), do:
if i + 1 < x, then:
mat[i + 1, j] = minimum of (mat[i + 1, j], mat[i, j] + (1 if grid[i + 1, j] is same as '#' AND grid[i, j] is same as '.'))
if j + 1 < y, then:
mat[i, j + 1] = minimum of (mat[i, j + 1], mat[i, j]+(1 if grid[i, j + 1] is same as '#' AND grid[i, j] is same as '.'))
return mat[x - 1, y - 1]示例
讓我們看看下面的實現來更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(int x, int y, vector<string> grid){
vector<vector<int>> mat(x, vector<int>(y, 100));
if(grid[0][0] == '#')
mat[0][0] = 1;
else
mat[0][0] = 0;
for(int i = 0; i < x; i++){
for(int j = 0; j < y; j++){
if(i + 1 < x){
mat[i + 1][j] = min(mat[i + 1][j], mat[i][j] + (grid[i + 1][j] == '#' && grid[i][j] == '.'));
}
if(j + 1 < y){
mat[i][j + 1] = min(mat[i][j + 1],mat[i][j]+(grid[i][j + 1] == '#' && grid[i][j] == '.'));
}
}
}
return mat[x - 1][y - 1];
}
int main() {
int x = 4, y = 4;
vector<string> grid = {"..#.", "#.#.", "#.##", "###."};
cout<< solve(x, y, grid);
return 0;
}輸入
4, 4, {"..#.", "#.#.", "#.##", "###."}輸出
1
更新於：2022年3月2日
瀏覽量：130
廣告