严禁加班，经历人生第一次被赶出公司，多家企业开启反内卷。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

最近关于大疆不强制 9 点上班，强制 9 点下班的消息冲上热搜，一到晚上9点，大疆的主管和HR分三轮赶人下班，禁止员工加班，9点以后，HRBP开始扫雷式赶人，他们背着“必须清场”的KPI。深圳总部实行赶人策略，上海区域更直截了当，办公楼到晚上9点准时关灯。

而美的从上周起就开始提倡各部门领导严谨控制加班，规定18:20不允许有人还在公司加班，同时也禁止了员工就餐后再返回工位继续加班的现象。一到下班时间，HR就会挨着部门催促员工抓紧时间下班。

这么好的事早几年就应该执行，本来三个人的活硬是让两个人加班干出来，回归到8小时工作制就会多出很多岗位，现在每年有一千多万毕业大学生，实行8小时工作制也可以促进大学生就业率。

有的人可能会担心，制造行业员工的收入主要靠加班，如果没有加班，只拿基本工资，估计难以生存，我觉得吧这个事有利有弊，但我还是支持8小时工作制。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第79题：单词搜索。

问题描述

来源：LeetCode第79题

难度：中等

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true

示例2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false

• m == board.length

• n = board[i].length

• 1 <= m, n <= 6

• 1 <= word.length <= 15

• board 和 word 仅由大小写英文字母组成

问题分析

这题让判断网格中是否存在要查找的单词，也没有告诉单词的起始位置在网格中的什么地方，我们以网格中的每一个位置当做起始位置来进行搜索。题中说的相邻是指水平和垂直方向，也就是从每个位置的上下左右四个方向进行搜索。

这是一道回溯算法题，如果从某个位置开始搜索，要注意一个位置不能重复搜索，所以搜索过之后要把它标记一下，题中说了字符串仅由大小写英文字母组成，标记的字符只要不是大小写英文字母就可以。沿着某条路径搜索完之后如果没有找到，需要撤销标记。

JAVA：

public boolean exist(char[][] board, String word) {     char[] chars = word.toCharArray();     // 遍历矩阵中的所有位置，以每一个位置为起始点进行查找。     for (int i = 0; i < board.length; i++)         for (int j = 0; j < board[0].length; j++) {             // 以位置[i,j]为起始点查找，如果找到，直接返回true。             if (dfs(board, i, j, chars, 0))                 returntrue;         }     returnfalse; } // 方向数组 int[][] dirs = newint[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; private boolean dfs(char[][] board, int i, int j, char[] word, int index) {     if (index == word.length) // 要查找字符串中的所有字符都查找完了。         returntrue;     // 不能越界     if (i < 0 || j < 0 || i >= board.length || j >= board[0].length)         returnfalse;     if (board[i][j] != word[index])         returnfalse;     char tmp = board[i][j];// 先把当前位置的字符保存下来     board[i][j] = '#';// 修改当前位置的字符，只要不是大小写字符都可以     for (int[] dir : dirs) {// 沿着当前位置的上下左右四个方向查找。         int x = i + dir[0];         int y = j + dir[1];         // 如果有一个方向能查找成功，直接返回true         if (dfs(board, x, y, word, index + 1))             returntrue;     }     board[i][j] = tmp;// 还原。     returnfalse; }

C++：

public:     bool exist(vector

 > &board, string word) {         // 遍历矩阵中的所有位置，以每一个位置为起始点进行查找。         for (int i = 0; i < board.size(); ++i) {             for (int j = 0; j < board[0].size(); ++j) {                 // 以位置[i,j]为起始点查找，如果找到，直接返回true。                 if (dfs(board, i, j, word, 0))                     returntrue;             }         }         returnfalse;     }     constint dirs[4][2] = {{0,  1},                             {0,  -1},                             {1,  0},                             {-1, 0}}; private:     bool dfs(vector

 > &board, int i, int j, string &word, int index) {         if (index == word.size()) // 要查找字符串中的所有字符都查找完了。             returntrue;         // 不能越界         if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size())             returnfalse;         if (board[i][j] != word[index])             returnfalse;         char tmp = board[i][j];// 先把当前位置的字符保存下来         board[i][j] = '#';  // 修改当前位置的字符，只要不是大小写字符都可以         for (constauto &dir: dirs) {// 沿着当前位置的上下左右四个方向查找。             int x = i + dir[0];             int y = j + dir[1];             // 如果有一个方向能查找成功，直接返回true             if (dfs(board, x, y, word, index + 1))                 returntrue;         }         board[i][j] = tmp;  // 恢复原字符         returnfalse;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。