数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给定从路径中 C++ 中停止的最小数量
问题陈述
- 在二维空间中有许多点需要按特定顺序访问。
- 从一点到另一点的路径始终选择为最短路径，并且路径段始终与网格线对齐。
- 我们得到了为访问点而选择的路径。我们需要告诉生成给定路径所需的最少点。
算法
1. We can solve this problem by observing the pattern of movement when visiting the stop 2. If we want to take the shortest path from one point to another point, then we will move in either one or max two directions
示例
#include <bits/stdc++.h>
using namespace std;
int getMinStops(string path) {
int n = path.length();
map<char, int> directionMap;
int stops = 1;
for (int i = 0; i < n; ++i) {
char direction = path[i];
directionMap[direction] = 1;
if ((directionMap['L'] && directionMap['R']) ||
(directionMap['U'] && directionMap['D'])) {
directionMap.clear();
++stops;
directionMap[direction] = 1;
}
}
return stops + 1;
}
int main() {
string path = "LLUUULLDD";
cout << "Minimum stops = " << getMinStops(path) << endl;
return 0;
}当您编译并执行上面的程序时，它会生成以下输出
输出
Minimum stops = 3
更新于： 23-Dec-2019
115次浏览
广告