之前上海一家外包公司的一位程序员，在项目结束后，被通知去宝山一处办公地报到，在那里，他的工作内容主要是参加培训、撰写心得等。相当于不在写代码了，脱离了实际岗位。
据说这家外包公司有一套特殊的管理模式，当程序员从外部项目撤下后，会被统一安排到外包公司的办公地址进行统一管理，并且办公区域还安装了摄像头，公司人事部门专门派人盯管，对员工进行考勤管理和监控查看。
随后在外包办公地工作三个月后，外包公司与该程序员解除了劳动关系，理由是“擅离工作岗位”，“工作时间吃外卖”以及“未经批准在工作场地使用个人电脑设备”。
该程序员于是申请劳动仲裁，要求外包公司支付违法解除劳动合同赔偿金113000余元。在仲裁请求被驳回后，该程序员起诉到法院。最终法院判决，外包公司的解除行为构成违法解除，应向该程序员支付赔偿金113000余元。
我的建议是外包公司能不去就尽量不要去，他们本来就是靠卖人头来赚钱了，当项目结束的时候，你已经不能在为他们挣钱了，所以被裁也是在所难免的，如果能给赔偿还好，就怕遇到这样故意找个借口说你违反公司规定，无故把你裁掉。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第1091题：二进制矩阵中的最短路径，难度是中等。
给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短畅通路径的长度。如果不存在这样的路径，返回 -1 。二进制矩阵中畅通路径是一条从左上角单元格（即，(0, 0)）到右下角单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
1.路径途经的所有单元格的值都是 0 。
2.路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度是该路径途经的单元格总数。
示例1：
输入：grid = [[0,1],[1,0]] 输出：2
示例2：
输入：grid = [[0,0,0],[1,1,0],[1,1,0]] 输出：4
n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] 为 0 或 1
问题分析
这题说的是找一条从左上角到右下角的最短路径，在矩阵中只有 0 可以通过，1 不能通过。从起始点如果我们把所有的能走的位置都连上，我们会发现他会构成一个图，这个就和迪杰斯特拉算非类似了。
不同的是迪杰斯特拉算法中边的权值一般都是不同的，而这里图中的所有边的权值都是 1 。这里我们从起始点开始，使用BFS（宽度优先搜索）来计算到终止点的最短路径。关于BFS的知识我们已经讲过很多了，一般配合着队列来使用，具体也可以看下前面讲的。
JAVA：
// 查找最短路径，看作是一个无向图，边的权值都是 1 。
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid[0][0] == 1)// 如果起始点是 1 ，则走不通，返回 -1 。
return -1;
int m = grid.length, n = grid[0].length;
Queue q = new LinkedList<>();// 创建队列
q.offer(newint[]{0, 0});// 起始点添加到队列中
boolean[][] vis = newboolean[m][n];// 记录当前位置是否被访问过
vis[0][0] = true;// 标记起始点被访问过
int level = 1;// BFS记录访问了多少层
// 8个方向
int[][] dirs = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1},};
while (!q.isEmpty()) {
int size = q.size();// 每层节点个数
while (size-- > 0) {
int[] pos = q.poll();// 节点出队
if (pos[0] == m - 1 && pos[1] == n - 1)// 如果到达右下角，则返回结果
return level;
for (int[] dir : dirs) {// 遍历当前位置的8个方向
int x = pos[0] + dir[0];
int y = pos[1] + dir[1];
// 不能越界，并且没有被访问过，且必须为 0 才能访问。
if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y] || grid[x][y] != 0)
continue;
q.offer(newint[]{x, y});// 新个位置添加到队列中
vis[x][y] = true;// 新的位置标记为访问过。
}
}
level++;
}
return -1;
}
C++：
public:
int shortestPathBinaryMatrix(vector> &grid) {
if (grid[0][0] == 1)// 如果起始点是 1 ，则走不通，返回 -1 。
return-1;
int m = grid.size(), n = grid[0].size();
queue
int
,
int
>> q;
// 创建队列
q.emplace(
0
,
0
);
// 起始点添加到队列中
vector> vis(m, vector(n, false))
;
// 记录当前位置是否被访问过
vis[
0
][
0
] =
true
;
// 标记起始点被访问过
int
level =
1
;
// BFS记录访问了多少层
// 8个方向
vector
int
,
int
>> dirs = {
{
-1
,
0
}, {
-1
,
1
}, {
0
,
1
}, {
1
,
1
},
{
1
,
0
}, {
1
,
-1
}, {
0
,
-1
}, {
-1
,
-1
}
};
while
(!q.empty()) {
int
size = q.size();
// 每层节点个数
while
(size-- >
0
) {
pair<
int
,
int
> pos = q.front();
q.pop();
// 节点出队
if
(pos.first == m -
1
&& pos.second == n -
1
)
// 如果到达右下角，则返回结果
return
level;
for
(
auto
[dx, dy]: dirs) {
// 遍历当前位置的8个方向
int
x = pos.first + dx;
int
y = pos.second + dy;
// 不能越界，并且没有被访问过，且必须为 0 才能访问。
if
(x <
0
|| x >= m || y <
0
|| y >= n || vis[x][y] || grid[x][y] !=
0
)
continue
;
q.emplace(x, y);
// 新个位置添加到队列中
vis[x][y] =
true
;
// 新的位置标记为访问过。
}
}
level++;
}
return
-1
;
}
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。
热门跟贴