阿里校招真题+参考代码

树上最短链

【题目描述】

在一个地区有n个城市以及n-1条无向边，每条边的时间边权都是1，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。

现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。

但是小强不喜欢走特别远的道路，所以他想知道时间花费最小是多少。

输入描述：

第一行一个正整数n，含义如题面所述。

第二行n个正整数Ai，代表每个城市的等级。

接下来n-1行每行两个正整数u，v代表一条无向边。

保证给出的图是一棵树。

1≤n≤5000

1≤u，v≤n

1≤Ai≤109

输出描述：

仅一行一个整数代表答案，如果无法满足要求，输出 -1 。

输入样例：

1 2 1

1 2

2 3

输出样例：

【解题思路】

数据量比较小，直接dfs即可。

【参考代码】

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, a[5005], root, ans = 1e9;
vector<int> e[5005];
void dfs(int r, int f, int deep) {
if (r != root && a[r] == a[root])
ans = min(ans, deep);
for (int i = 0; i < e[r].size(); i++)
if (e[r][i] != f)
dfs(e[r][i], r, deep + 1);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int i, j, x, y;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i < n; i++) {
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
for (i = 1; i <= n; i++) {
root = i;
dfs(i, 0, 0);
}
cout << (ans == 1e9 ? -1 : ans);
return 0;
}

对称飞行器

【题目描述】

小强在玩一个走迷宫的游戏，他操控的人物现在位于迷宫的起点，他的目标是尽快的到达终点。

每一次他可以选择花费一个时间单位向上或向下或向左或向右走一格，或是使用自己的对称飞行器花费一个时间单位瞬移到关于当前自己点中心对称的格子，且每一次移动的目的地不能存在障碍物。

具体来说，设当前迷宫有n行m列，如果当前小强操控的人物位于点A(x,y)，那么关于点 A 中心对称的格子B(x',y') 满足x+x'=n+1且y+y'=m+1。

需要注意的是，对称飞行器最多使用5次。

输入描述：

第一行两个空格分隔的正整数n，m分别代表迷宫的行数和列数。

接下来n行每行一个长度为m的字符串来描述这个迷宫。

其中

. 代表通路。

# 代表障碍。

S 代表起点。

E 代表终点。

保证只有一个S和一个E 。

2≤n，m≤500

输出描述：

仅一行一个整数表示从起点最小花费多少时间单位到达终点。

如果无法到达终点，输出 -1 。

输入样例：

4 4

#S..

E#..

#...

....

输出样例：

说明

一种可行的路径是用对称飞行器到达(4,3)再向上走一步，再向右走一步，然后使用一次对称飞行器到达终点。

【解题思路】

三维广搜，需要额外处理对称位置的转移。

【参考代码】

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node {
int x, y, t;
};
int n, m, sx, sy, ex, ey, v[505][505][6];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
char a[505][505];
queue<node> q;
void bfs(int x, int y) {
v[x][y][0] = 1;
int i, j, t, nx, ny;
q.push({x, y, 0});
while (q.size()) {
x = q.front().x, y = q.front().y, t = q.front().t;
q.pop();
for (i = 0; i < 5; i++) {
if (i == 4) {
if (t < 5)
nx = n + 1 - x, ny = m + 1 - y, t++;
else
continue;
} else
nx = x + dx[i], ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#' &&
v[nx][ny][t] == 0) {
if (i == 4)
v[nx][ny][t] = v[x][y][t - 1] + 1;
else
v[nx][ny][t] = v[x][y][t] + 1;
if (nx == ex && ny == ey)
return;
q.push({nx, ny, t});
}
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int i, j, ans = -1;
cin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] == 'S')
sx = i, sy = j;
if (a[i][j] == 'E')
ex = i, ey = j;
}
bfs(sx, sy);
for (i = 0; i < 6; i++)
if (v[ex][ey][i])
ans = v[ex][ey][i] - 1;
cout << ans;
return 0;
}