华为2021-10-13机试
第一题（100分）
问题描述：
小明家有很大的房子，有很多房间.房间之间可能有门相通，先输入初始房间编号roomA(整数类型），再输入需要到达的房间编号roomB(整数类型）。
然后输入一个正整数N（N<=100），最后输入N对数据，表示房间之间有门相通。
问：从roomA到roomB最少需要开多少扇门？
例如—— 输入： 1 5 5
1 2
2 3
3 4
2 5
4 5
输出： 2（即1->2->5）
补充：题目没说不可达的情况，我觉得不可达输出-1较合理。
解题思路： 可以直接建模为一个无向连通图，使用广度优先搜索就可以把最少开门数找出来。
C++代码：
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include "stdio.h"
using namespace std;
int froom, eroom, N, roomA, roomB;
int front, rear;
bool arc[205][205]; //邻接矩阵，用于存放图中顶点之间的关系
bool vis[205]; //存放顶点是否已经访问信息
vector<int> vertex; //存放顶点实际编号信息
int que[205]; //广度优先遍历的队列信息
int bfsearch(int fr){
//从顶点fr进行广度优先遍历
int ans = 0, sz = vertex.size(), v = -1;
int step[205];//记录走到的步数
memset(step, 0, sizeof(step));
for(int i = 0; i < sz; i++){
if(vertex[i] == fr){
v = i;
break;
}
}
if(v == -1) return -1;//不可走
front = rear = -1; vis[v] = 1; que[++rear] = v;
while(front <= rear){
int i;
v = que[++front]; //出队
for(i = 0; i < sz; i++){
if(arc[v][i] == 1 && !vis[i]){
que[++rear] = i;
vis[i] = 1;
step[rear] = step[front]+1; //单层找到了长度加1
if(vertex[i] == eroom)
return step[rear];
}
}
}
return -1; //找不到
}
int main(){
while(cin >> froom >> eroom >> N){
memset(arc, 0, sizeof(arc));
memset(vis, 0 , sizeof(vis));
memset(que, 0 , sizeof(que));
vertex.clear();
int ra, rb, shortestDis;
for(int i = 0; i < N; i++){
cin >> roomA >> roomB;
int sz = vertex.size();
for(ra = 0; ra < sz; ra++){
if(vertex[ra] == roomA)
break;
}
if(ra == sz){//roomA不在顶点列表内
vertex.push_back(roomA);
}
sz = vertex.size();
for(rb = 0; rb < sz; rb++){
if(vertex[rb] == roomB)
break;
}
if(rb == sz){//roomB不在顶点列表内
vertex.push_back(roomB);
}
arc[ra][rb] = 1;
arc[rb][ra] = 1;
}
shortestDis = bfsearch(froom);
if(shortestDis == -1){
cout << "-1" << endl;//数据错误或者找不到
}else{
cout << shortestDis << endl;
}
}
return 0;
} 第二题（200分）
问题描述：
大概说的是有一个长为m，宽为n的陆地，中间有些湖不可以走。陆地版块的左上角坐标为(0,0)，右上角坐标为(0,n-1)，左下角坐标为(m-1,0)，右下角坐标为(m-1,n-1)。输入陆地的长、宽m和n （m, n <= 11），输入起始点的坐标和终止点的坐标，接着输入一个正整数N，下面N行是湖的坐标对。规定只能往上、往下、往右和往左移动。
问：从起始点到终止点的最短路径有多少条？最短路径的长度是多少？
补充：问题没说不可走或者数据错误的情况，对于这两种情况输出 0 0 即可.
例如——输入： 5 5
0 1
2 1
1
1 1
输出： 2 4
解题思路：这个问题也是一个图类型的问题，可以先使用广度优先搜索把起始点到终止点的最短路径长度找出来，然后再使用深度优先搜索去遍历图，把其中起点到终点刚好路径长度为最短路径长度的路径结果统计下就行。
C++代码：
#include<iostream>
#include<cstring>
using namespace std;
int m, n, sx, sy, ex, ey;
int arr[12][12], vis[12][12];
int hu;
int dr[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
int minluj, ans;
int bfs(int x, int y){
int front = -1, rear = -1, s = 0;
int que[105][2];
int step[105];//记录走到的步数
memset(step, 0, sizeof(step));
if(x == ex && y == ey) return 0;
if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || arr[x][y]) return -1;
que[++rear][0] = x; que[rear][1] = y;
vis[x][y] = 1;
while(front <= rear){
x = que[++front][0]; y = que[front][1];
for(int p = 0; p < 4; p++){
int vx = x + dr[p][0], vy = y + dr[p][1];
if(vx < 0 || vx >= n || vy < 0 || vy >= m || vis[vx][vy] || arr[vx][vy])
continue;
vis[vx][vy] = 1;
que[++rear][0] = vx; que[rear][1] = vy;
step[rear] = step[front] + 1;
if(vx == ex && vy == ey)
return step[rear];
}
}
return -1; //找不到
}
void dfs(int x, int y, int step){
if(x == ex && y == ey){
if(step == minluj)
ans++;
return;
}else{
for(int p = 0; p < 4; p++){
int vx = x + dr[p][0], vy = y + dr[p][1];
if(vx < 0 || vx >= n || vy < 0 || vy >= m || vis[vx][vy] || arr[vx][vy])
continue;
vis[vx][vy] = 1;
dfs(vx, vy, step+1);
vis[vx][vy] = 0;
}
}
}
int main(){
while(cin >> m >> n){
memset(arr, 0, sizeof(arr));
memset(vis, 0 , sizeof(vis));
minluj = 0, ans = 0;
cin >> sx >> sy;
cin >> ex >> ey;
cin >> hu;
int x, y;
for(int i = 0; i < hu; i++){
cin >> x >> y;
arr[x][y] = 1; //1表示不可走
}
minluj = bfs(sx, sy);
if(minluj == -1){
cout << "0 0" << endl;//数据错误或者不可走
}else{
memset(vis, 0 , sizeof(vis));
vis[sx][sy] = 1;
dfs(sx, sy, 0);
cout << ans << " " << minluj << endl;
}
}
return 0;
} 第三题（300分） 第三题是牛客上的一道原题
问题描述：
链接：https://www.nowcoder.com/questionTerminal/5f76ce2a25744d96bb9797e03c523302?orderByHotValue=1&page=1&onlyReference=false
来源：牛客网
来源：牛客网
给定一个非空字符串, 按照如下方式编码, 使得编码后长度最小, 返回编码后的长度:
编码规则为: k[encoding_string], 表示重复k次encoding_strng,
例如'abcdefabcdefabc'可表示为'2[abcdef]abc', 但是'aaa'仅能编码成'aaa',
因为len('3[a]')>len('aaa').
补充:
1. k为正整数, []内的encoding_string不得含有空格不得为空;
2. []内的encoding_string 本身可以为编码过的字符串, 例如'abcdabcdeabcdabcde' 可以编码为 '2[abcdabcde]'(编码后长度从18减少到12), []内的'abcdabcde'又可以编码为 '2[abcd]e', 最终编码为 '2[2[abcd]e]', 编码后长度为11, 应返回11; 这个编码路径也能是: 'abcdabcdeabcdabcde' -> '2[abcd]e2[abcd]e' -> '2[2[abcd]e]';
2. 输入字符串为全小写英文字母, 长度<=160;
3. 如果编码后长度没有更小, 则保留原有字符串;
输入：一行数据，表示输入字符串
输出：一个字符串表示编码后长度
例如——
输入： aaa 输出：3 因为3[a]是4个字符比aaa的字符数要多
输入：aaaaa 输出：4 因为5[a]是4个字符比aaaaa的字符数要少
输入：aabcaabcd 输出：2[aabc]d
解题思路：使用区间动态规划求解，用一个二维数组string dp[][]来存储区间的最短字符串形式，即dp[i][j]表示[i, j]区间的最短字符串形式。
最终结果输出dp[0][n-1]的长度即可，其中n是输入字符串的长度。
C++代码：
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include "stdio.h"
using namespace std;
string encode(string s){
int n = s.length(); //求出s的大小，用于定义数组大小
vector<vector<string>> dp(n, vector<string>(n, ""));//定义了一个二维数组dp,dp[i][j]表示[i,j]范围内的字符串缩写形式
for(int step = 1; step <= n; step++){//step区间长度，i为区间起始点，j为区间终止点
for(int i = 0; i+step-1 < n; i++){
int j = i + step - 1;
dp[i][j] = s.substr(i, step);//将s从i开始取step长度的子字符串赋给dp[i][j]
for(int k = i; k < j; k++){
string left = dp[i][k], right = dp[k+1][j];
if(left.length() + right.length() < dp[i][j].length()){
dp[i][j] = left + right;
}
}
string t = s.substr(i, step), replace = "";
auto pos = (t + t).find(t, 1);
if(pos >= t.length()) replace = t;
else replace = to_string(t.length()/pos) + '[' + dp[i][i + pos -1] + ']';
if(replace.length() < dp[i][j].length()) dp[i][j] = replace;
}
}
return dp[0][n-1];
}
int main(){
string s;
while(cin >> s){
string result = "";
result = encode(s);
cout << result.length() << endl;
}
return 0;
} 
