8.31号华为机试
1.字符串压缩（题目较长，代码也长，有时间更新）
给你一句话，然后再给你一个字典，请把这句话中的所有单词替换成该单词在字典中的索引，不区分大小写。句子中包括",."以及空格等符号，这些符号不变，且""之中的单词不会被替换。
例子：
句子：Hello，I will go to the "New World Park".
字典：hEllo TO park
输出：0，I will go 1 the "New World Park".
park在""内，因此不替换。
时间久了，具体代码忘干净了，提供个思路：
1.把字典里面的所有单词都转化为小写（大写）字母单词，并加入到hash表中，
2.分割句子，把句子隔成一个一个的单词，遇到“就跳，一直跳到下一个”停止，
3.每一个分割的单词，转成小写（大写）单词，并在hash表中检索，然后替换
大概五六十行代码
2.士兵走出迷宫：
给你一个迷宫矩阵，从迷宫的左上角走到右下角，请输出最短的通行路径。（给出的迷宫矩阵一定可以走到终点）
其中，值为1时该位置可以走通，值为2时是墙，该位置无法通过，值为3时为陷阱，该位置可以走通，但是要多加三个单位的时间，值为4时，该位置是炸弹，可以走通，而且可以把周围相邻的四堵墙炸开。
例子：
输入：
5 5
1 2 2 3 4
1 2 2 3 4
1 2 2 3 4
1 2 2 3 4
1 1 1 1 1
输出：
（0，0）
（1，0）
（2，0）
（3，0）
（4，0）
（4，1）
（4，2）
（4，3）
（4，4）
题解：
利用dfs+记忆化搜索
代码：（靠记忆回想，有bug，不过总体思路应该差不多，可作为参考）
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int best_step = INT_MAX;;
vector<vector<int>> maze;
vector<pair<int, int>> temp_path;
vector<pair<int, int>> best_path;
void dfs(int i, int j, int cur_step);
int main(void){
//参数输入
cin >> n;
cin >> m;
maze = vector<vector<int>>(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> maze[i][j];
cout << maze[i][j] << ' ';
}
}
//深度递归遍历+记忆化搜索
dfs(0, 0, 0);
cout << "gello!" << endl;
cout << best_path.empty() << endl;
//输出
for (auto& x : best_path) {
cout << "(" << x.first << "," << x.second << ")" << endl;
}
getchar();
}
void dfs(int i, int j, int cur_step) {
//后面会多次用到节点值，因此取出节点值
int cur = maze[i][j];
//去除非法的道路以及墙
if (i < 0 || j < 0 || i >= n || j >= m || cur == 2) {
return;
}
//找到中点，直接查看结果，此处有一个cur_step和best_step，是因为有陷阱，可能路径最短，但是
if ((i == n - 1) && (j == m - 1)){
if (cur_step < best_step) {
best_path = temp_path;
}
}
//如果此节点为陷阱，则将总步数+3
if (cur == 3) {
cur_step = cur_step + 3;
}
//保存此节点的周围节点值，以防被炸后可以还原
int pre_a;
int pre_s;
int pre_d;
int pre_w;
//此处我忘记题目能不能炸陷阱了，就当能炸，全都设为1
if (cur == 4) {
if (i > 0) {
pre_a = maze[i - 1][j];
maze[i - 1][j] = 1;
}
if (j > 0) {
pre_w = maze[i][j - 1];
maze[i][j - 1] = 1;
}
if (i < n) {
pre_d = maze[i + 1][j];
maze[i + 1][j] = 1;
}
if (j < m) {
pre_s = maze[i][j + 1];
maze[i][j + 1] = 1;
}
}
//对此节点的步数、节点值进行更改，并将该节点加入模拟栈中
cur_step++;
maze[i][j] = 2;
temp_path.push_back({ i, j });
//深度遍历
dfs(i - 1, j, cur_step);
dfs(i + 1, j, cur_step);
dfs(i, j - 1, cur_step);
dfs(i, j + 1, cur_step);
//还原此节点
maze[i][j] = cur;
//将炸了的节点全部还原
if (cur == 4) {
if (i > 0) {
maze[i - 1][j] = pre_a;
}
if (j > 0) {
maze[i][j - 1] = pre_w;
}
if (i < n) {
maze[i + 1][j] = pre_d;
}
if (j < m) {
maze[i][j + 1] = pre_s;
}
}
//出栈
temp_path.pop_back();
} 3.开车到达终点的最短时长。 你有一辆最大1000公里续航的电动车，电动车车速恒定为100公里/小时，即你的车子最多能开10小时。现在，你需要从A地到达B地，中间可能需要多次充电才能到达，这意味着你需要到达充电站进行充电续航。每次充电前需要排队等待，排队时间恒定，排队结束后，充电另需一小时。接下来给你一组数据，第一行第一个数是A、B两地的距离d，第二个数是充电站的总个数m；第二行到接下来的第m+1行，每行都有两个数据，第一个数据为此充电桩距离A始发地的距离，第二个数据为需要排队的等待时间。请你计算出从A地到B地的最短时间。
例子：
输入：
1500 4
300 0
600 1
1000 0
1200 1
输出：
输出：
16（行驶1000公里到达第三个站点，用时10小时，然后充电1小时，继续行驶5小时到达终点，总路程1500公里，总时间10+1+5=16）
题解：
利用动态规划+加回退搜索
把起始点设为0，每次到达一个新的站点，便进行回退搜索，一直搜索到1000公里以内且距离最远的充电站点k，然后从k站点开始遍历，一直遍历到当前站点，找到最短到达当前站点的时间，然后保存到当前站点的时间数组ans中，不断循环遍历，最终遍历到终点。
代码：（靠记忆回想，有bug，不过总体思路应该差不多，可作为参考）
#define DEBUG 1
#if DEBUG
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
int n, m;
//参数输入
cin >> n;
cin >> m;
//初始化站点数组，将起点和终点也纳入数组中
vector<vector<int>> f(m+2, vector<int>(2));
//起点的距离和等待时间都设为0
f[0][0] = 0;
f[0][1] = 0;
//终点的距离设为n，等待时间设为0
f[m+1][0] = n;
f[m+1][1] = 0;
//开始加入各个站点
for (int i = 1; i < m+1; i++) {
cin >> f[i][0];
cin >> f[i][1];
cout << f[i][0] << ' ';
cout << f[i][1] << ' ';
}
//初始化到达站点的时间，将起点和终点也纳入数组中
vector<int> ans(m + 2);
ans[0] = 0;
//开始计算各个站点
for (int i = 1; i < m + 2; i++) {
//将所有距离在1000以内的站点找出来
int k = i - 1;
while (k > 0 && (f[i][0] - f[k][0] < 1000)){
k--;
}
//这里除了起始站点以外，多超了一个站点，因此k需要加一
if (k != 0) {
k++;
}
//对每个可以直接到达的站点进行遍历，找出最小的时间站点
int min_time = INT_MAX;
for (; k < i; k++) {
int cur_time = (f[i][0] - f[k][0]) / 100 + ans[k] + f[i][1];
if (k != 0) {
cur_time++;
}
min_time = min(min_time, cur_time);
}
}
getchar();
cout << ans[m+1] << endl;
getchar();
}
#endif // DEBUG 
