数据结构
网络
关系数据库管理系统(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
广告