阿里巴巴2018春招笔试编程题

昨天做了阿里巴巴春招Java研发岗位的笔试，首先还是想要吐槽一下这次笔试，选择题各种机器学习、神经网络，外加概率题、智力题，就是没有任何一个Java相关的题目，让我不禁怀疑是不是投错了岗位。编程题也总觉得有些细节描述不是特别准确，甚至可能有些小的差错。最终我做的可以说是很烂了，这里简要记录一下看了各种讨论和资料后，想出的两道编程题的解法。

第一题

在自动化仓库中有若干障碍物，机器人需要从起点出发绕过这些障碍物到终点搬取货柜，现试求机器人从起点运动到终点用时最短的路径。 已知机器人只能沿着东西方向或南北方向移动，移动的速度为1m/s，机器人每转向90度需要花费1s。

输入：

第一行：起点位置坐标及机器人朝向，如：
1 0 EAST
代表机器人初始坐标为x=1,y=0，机器人面朝东方
第二行：终点位置坐标及机器人朝向，如：
0 2 WEST
代表机器人需要移动至点x=0,y=2，且面朝西方
接下来输入的是地图：
首先是两个数字r,c，代表有地图数据有多少行与多少列，如：
2 3
0 1 0
0 0 0
其中，左上角为坐标原点，从左向右为x轴增大的方向是东方，从上到下为y轴增大的方向是南方。
地图中1代表有障碍物，机器人不能前往，0代表无障碍物机器人可以前往 地图中相邻的每两个点之间的距离为1m。
0 <= l,w <= 128

输出：

机器人从起点移动到终点所需要的最短秒数，当不可达时输出65535

算法：

(BFS) O(n2)$O(n^2)$

看到题目第一眼感觉应该是个宽搜的题，但是这里转身是有时间代价的，所以需要做一定的转化。具体转化方式是看到牛客网讨论区有人说到对map[r][c][4]宽搜，想到确实应该可以把方向也变成一个维度，在三维的空间里进行宽搜，在每个点有三种方式可选：向前走，向左转，和向右转，所以思路就比较清晰了。

代码（不一定正确）：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int get_dir(char *dir) {
    if (strcmp(dir, "EAST") == 0)
        return 0;
    if (strcmp(dir, "SOUTH") == 0)
        return 1;
    if (strcmp(dir, "WEST") == 0)
        return 2;
    return 3;
}

struct Point
{
    int x, y, d;
    int step;
    Point(int x, int y, int d, int step) : x(x), y(y), d(d), step(step) {}
};

int main()
{
    int sx, sy, sd, tx, ty, td;
    char s_dir[10], t_dir[10];
    cin >> sx >> sy >> s_dir;
    cin >> tx >> ty >> t_dir;
    sd = get_dir(s_dir);
    td = get_dir(t_dir);
    int map[130][130][4];
    int r, c;
    cin >> r >> c;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cin >> map[i][j][0];
            for (int k = 1; k < 4; ++k)
                map[i][j][k] = map[i][j][0];
        }
    }
    queue<Point> my_queue;
    bool visited[130][130][4];
    memset(visited, false, sizeof(visited));
    Point start(sx, sy, sd, 0);
    my_queue.push(start);
    while (!my_queue.empty()) {
        Point point = my_queue.front();
        if (point.x == tx && point.y == ty && point.d == td) {
            cout << point.step << endl;
            break;
        }
        my_queue.pop();
        int nx = point.x, ny = point.y, nd = point.d;
        switch (point.d) {
        case 0: nx = point.x + 1; break;
        case 1: ny = point.y + 1; break;
        case 2: nx = point.x - 1; break;
        default: ny = point.y - 1; break;
        }
        int step = point.step + 1;
        if (nx >= 0 && nx < c && ny >= 0 && ny < r
            && map[ny][nx][nd] == 0 && !visited[ny][nx][nd]) {
            visited[ny][nx][nd] = true;
            my_queue.push(Point(nx, ny, nd, step));
        }
        nx = point.x, ny = point.y;
        int d[2] = { -1, 1 };
        for (int i = 0; i < 2; ++i) {
            nd = (point.d + d[i]) % 4;
            if (!visited[ny][nx][nd]) {
                visited[ny][nx][nd] = true;
                my_queue.push(Point(nx, ny, nd, step));
            }
        }
    }
    if (my_queue.empty()) cout << 65535 << endl;
    return 0;
}

---

第二题

阿里巴巴客服管理员管理着 n 个客服小组，他需要为每一组安排客服24小时值班。为简单起见，假设每组只有2个客服，一天只需要1个客服上班，并且一些客服由于某些原因不能在同一天上班。

我们已经对客服进行了编号，第 i (i>=1&&i<=n) 个组的客服编号为 2*i-1 和 2*i 。并且知道了 m 种如下约束关系：客服编号 a 和客服编号 b 不能一起上班。

管理员需要聪明的你帮忙判断今天是否存在可行的方案，既满足 m 条约束关系，又能让每个组都有1个客服上班。

输入：

n (代表有 n 个组）
m (m 条约束关系），接下来会有 m 行
a, b (代表 a，b 两位客服标号不能同时上班)

输出：

判断有没有可行方案：如果不可行输出 no；如果可行输出 yes

样例：

输入：

4
3
1,4
2,3
7,3

输出：

yes

算法

(2-SAT) O(m)$O(m)$

总觉得碰到过许多次这样的题，但是每次遇到都是不会做，这次下来查了些资料，知道这一类问题叫做 2-SAT 问题，网上可以搜到很多资料。算法就是构造有向图，然后通过 tarjan 算法求得强连通分量，将图收缩，最后在得到的图中判断同一组的两个点是否在一个环上，如果是则问题无解；否则可通过拓扑排序得出问题的一个解。

代码

稍后补充……