机试题目一共四道：第一道是子矩阵最大值，考察最值和循环结构；第二道是结构体排序，涉及键值映射；第三道考察图的搜索算法，考察二维数组的存储和广度优先搜索；第四道是单源最短路径，主要是Dijkstra算法。
PART-01
第一题
以能源星球为背景，大致内容是某星球的能量散落在不同的区域，不同区域的能量值不同。矩阵代表不同区域的能量值，现要从矩阵中任意一点开始采集能源，能源采集最大值即为子矩阵各节点的值之和，求能源采集的最大值。
实例（根据回忆编写）：
输入：第一行输入矩阵行数n，矩阵列数m
[1，-3，7，9]
[6，-5，8，4]
[3，1，-9，3]
[15，10，2，-13]
输出：14
考场思路
暴力解，遍历矩阵，使用sum变量存储每轮矩阵和，使用maxSum变量计算sum最大值。
但需要注意的是只有在所有运算数值构成矩阵的情况下才能相加求和，如1、-3、7、9、6是不能相加的，因为这5个数无法构成矩阵。所以该题的难点在于如何判断相加的几个数能否构成子矩阵，以矩阵中某一值A[i][j]作为起始点，矩阵列长变化范围为[1,n-1-j]，矩阵行长变化范围为[1,n-1-i]。列长为c，行长为r时，子矩阵内包含的数值有A[i][j]、A[i][j+1]…A[i][j+c-1]，A[i+1][j]、A[i+1][j+1]…A[i+1][j+c-1]，……，A[i+r-1][j]、A[i+r-1][j+1]…A[i+r-1][j+c-1]。这些数值需使用两层嵌套循环表示，每个数值为A[i+r-1][j+c-1]，使用sum存储遍历到的所有数值的总和。
代码
#include<bits/stdc++.h> //万能头文件
#include<iostream>
using namespace std;
int main () {
int n, m;
cin >> n >> m;
int A[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> A[i][j];
}
}
int sum = 0;
int maxSum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int r = 1; r < n - 1; r++) {
for (int c = 1; c < n - 1; c++) {
sum += A[i+r-1][j+c-1];
}
}
maxSum = max (maxSum, sum);
}
}
return maxSum;
}
PART-02
第二题
以工业生产为背景，大致内容是工厂内又m台机器每隔一段时间会发出提醒，每台机器具有设备号Q_num和提醒时间Period，不同机器的设备号和提醒时间不同，所有机器从某时刻一同开始生产，求从生产时刻开始依次提醒的k台机器。
实例：
输入：2004 200
2005 300
2006 300
输出：2004、2004、2005、2006、2004、2005、2006
考场思路
暴力解，同一台机器的设备号可被重复输出，计算出每台机器0~k个提醒时间的时间值，共计算n=m*k次，将这n个数值从小到大排序后依次输出前k个提醒时间对应的设备号。
但是该问题的难点在于输出的是设备号，而非排序依据的时间值，所以需要建立设备号与时间值的映射关系。我使用了两个结构体，第一个结构体Machine记录初始m台机器的设备号和提醒时间，第二个结构体Record记录n个待排序提醒时间数值及对应的设备号。使用sort函数对Record结构体排序，输出前k个设备号。
代码
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
struct Machine {
int Q_num;
int Period;
};
struct Record {
int Q_num;
int Period;
};
bool cmp (const Machine& x, const Machine& y) {
return x.Period < y.Period;
}
int main () {
cin >> m >> k;
Machine machine[m];
int n = m * k;
Record record[n];
for (int i = 0; i < m; i++) {
cin >> machine[i];
}
vector<Record> queue;
Record temp;
for (int i = 0; i < m; i++) {
temp.Q_num = machine[i].Q_num;
for (int j = 0; j < k; j++) {
temp.Period = machine[i].Period * k;
queue.push_back(temp);
}
}
sort (queue, queue + m * k, cmp);
for (int i = 0; i < k; i++) {
cout << queue[i].Q_num << “ ”;
}
}
PART-03
第三题
题目是以草丛设置障碍物为背景，考察图的搜索，跟25年的滑冰题目类似。
这里对滑冰题目作出分析。
滑冰原题如下：
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
一个很滑的二维网格存在冰块障碍，问你是否能从给定位置开始，最终停在终点。图中‘#’为障碍，‘.’为空地。
由于场地很滑，每次往上下左右移动都会撞上障碍才停止，并且每次开始移动后，移动的起点会生成一个新的冰块障碍。
输出到达终点最小移动次数，如果不能到达终点则输出-1。
考场思路
图的最短路径问题，采用广度优先搜索，并且题目限制（二维网格）图的存储方式为顺序存储。程序首先需判断起点坐标到终点坐标之间是否存在路径，然后计算路径的最短值。
两个步骤采用不同编程思路。（1）判断是否存在路径采用类似深度遍历的思想，以起始单元格为中心，逐层向外遍历其所有的相邻单元格，如果能够到达终点，则起点与终点间存在路径。（2）计算路径最短值可以使用求最值的通用思路，每层不仅有一个单元格，但向外搜索的过程中每层只需记录到达该层单元格的最小值，每层单元格优先级相同，取所有到达该层的路径值的最小值。
代码
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define INT_MAX 1e5+5;
int main () {
int m, n;
cin >> m >> n;
int grid[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
}
}
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int vis[m][n];
memset(vis, 0, sizeof(vis));
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
dist[0][0] = 1;
cin >> si >> sj;
cin >> ei >> ej;
queue<pair<int, int>> queue;
queue.push({si, sj});
while (! queue.empty()){
auto& node = queue.front();
int x = node.first;
int y = node.second;
node.pop();
if (x == ei && y == ej) {
return dist[x][y];
}
for (int i = 0; i < 4; i++) {
if (x + dir[i][0] < 1 || y + dir[i][1] < 1 || x + dir[i][0] > m || y + dir[i][1] < n)
continue;
if (grid[x + dir[i][0]][y + dir[i][1]] == ‘#’ || dist[x + dir[i][0]][y + dir[i][1]] < dist[x][y] + 1)
continue;
dist[x + dir[i][0]][y + dir[i][1]] = dist[x][y] + 1;
queue.push({x + dir[i][0], y + dir[i][1]});
}
}
return -1;
}
PART-04
第四题
以城市送信为背景，大致内容是森林城市内各地点通过道路相连，但出于城市规划的考虑，并非每对地点两两之间都有道路，且不同道路通行所耗费的代价不同。某日，小熊邮差从邮局（视为地点1）出发，将今天的信件送到城市的第n户居民（视为地点n）手中。为了保证小熊花费的代价最小，求送信所需的最短时间。
考场思路
单源最短路径问题，且只需求出源结点与图中第n个结点的最短距离。做到本题时已经临近考试结束，时间不允许有太多思考，幸运的是考试允许携带3页A4纸资料，刚好我整理了Dijkstra算法的代码，所以抄写的现有代码。
Dijkstra算法的思路为遍历图中除源节点外的所有结点，设置到每个结点的距离初值，而后进行n-1次循环，每次循环都会找出当前与源结点距离最小的结点，若源结点经由该结点到达剩余结点的距离小于不经过该结点的距离，则更新，否则就会跳过。如此，即可计算出源节点到图中每个结点的最短距离，使用dist数组保存，dist[n]值即从结点1到结点n的最短时间。
代码
void Dijkstra (int n, int v, int dist[], int prev[], int **c) {
bool s[maxint];
for (int i = 1; i <= n; i++) {
dist[i] = c[v][i];
s[i] = false;
if (dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
}
dist[v] = 0;
s[v] = true;
for (int i = 1; i < n; i++) {
int tmp = maxint;
int u = v;
for (int j = 1; j <= n; j++) {
if ((! s[j]) && (dist[j] < temp)) {
u = j;
temp = dist[j];
}
s[u] = true;
for (int j = 1; j <= n; j++) {
if ((! s[j]) && (c[u][j] < maxint)) {
Type newdist = dist[u] + c[u][j];
if (newdist < dist[j]) {
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
}
int main () {
cin >> n;
int c[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> c[i][j];
}
}
int dist[n];
int prev[n];
Dijkstra (n, 1, dist, prev, **c);
cout >> dist[n];
}
