为什么复旦教授建议在洗澡时千万不要做人脸认证。|grid|人脸认证|复旦|算法

最近在网上看到一个新闻，中科院张军平教授提醒大家，千万不要在洗澡的时候去做人脸认证。他说：摄像头并不是只看到圆的这一块内容，屏幕上所显示的“摄像头的圆”其实是起了一个“掩码”的作用，实际上被拍到的画面不止于这个“圆”。

其实张教授说的非常对，所谓的人脸识别并不是只拍摄圆框内的图像，人脸识别它调用的是手机的相机，需要拍照权限，整个拍摄区域是一个矩形，也就是整个屏幕都能看到的区域，和平时拍照一样。而在人脸识别中的那个圆形图像主要是确认你不要偏的太远，所以很多人都认为相机是只抓取了圆形框的那一块，实际上这是不对的。

为什么我知道这么多，因为在很多年前公司做国内外贷款业务的时候，我做过人脸识别的功能，拍摄无关的区域我们会用图片把它盖上，给你看到的要么是一个圆形头像，要么是一个小的矩形，但拍摄之后我们还会对图像截取和压缩，截取的时候只截取矩形框内的图像，如果拍照的时候离的太远，是可以看到上半身的。

当时我们在服务器后台确实也看到不少光着膀子的。如果遇到那种图像不截取的，基本上你拍到的所有区域都是能看到的，所以大家人脸识别的时候最好还是要穿上衣服。

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

来看下今天的算法题，这题是LeetCode的第1559题：二维网格图中探测环，难度是中等。

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在相同值形成的环。

一个环是一条开始和结束于同一个格子的长度大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有相同的值。

同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。

如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。

示例1：

输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]] 输出：true 解释：如上图所示，有 2 个用不同颜色标出来的环：

示例2：

输入：grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]] 输出：true 解释：如上图所示，只有高亮所示的一个合法环：

m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid 只包含小写英文字母。

问题分析

这题让判断在矩阵中相同的字符是否可以构成环，解法比较多，可以使用并查集，也可以使用BFS或者DFS。我们按照矩阵的深度优先搜索（DFS）来解这道题。

首先从起始点开始搜索，只搜索字符相同的点，搜索的时候只能沿着当前位置的上下左右四个方向搜索，并且搜索的节点不能重复，也就是不能回退，

如果遇到某个点被搜索过，说明找到了一个环，直接返回true即可。否则继续遍历矩阵中下一个没有被搜索过的点，从该点继续搜索。

JAVA：

public boolean containsCycle(char[][] grid) {
    int m = grid.length, n = grid[0].length;
    boolean[][] vis = newboolean[m][n];// 记录当前位置是否被访问过
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!vis[i][j] && dfs(grid, vis, i, j, -1, -1, grid[i][j]))
                returntrue;
        }
    }
    returnfalse;
}


 // (pai,paj)表示上一个节点的坐标，ch表示本次搜索的字符必须和ch字符相同。
private boolean dfs(char[][] grid, boolean[][] vis, int i, int j, int pai, int paj, char ch) {
    // 边界条件判断
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != ch)
        returnfalse;
    if (vis[i][j]) // 已访问过该节点，说明存在环
        returntrue;
    vis[i][j] = true; // 标记当前节点为已访问
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 方向数组
    for (int[] dir : dirs) {
        int x = i + dir[0];
        int y = j + dir[1];
        if (x == pai && y == paj) // 跳过上一个节点（避免回退）
            continue;
        if (dfs(grid, vis, x, y, i, j, ch))// 上下左右四个方向只要有一个能找到环，则返回true
            returntrue;
    }
    returnfalse;
}

C++：

public:
    bool containsCycle(vector> &grid) {
        int m = grid.size(), n = grid[0].size();
        vector> vis(m, vector(n, false));// 记录当前位置是否被访问过
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!vis[i][j] && dfs(grid, vis, i, j, -1, -1, grid[i][j]))
                    return true;
            }
        }
        return false;
    }


 // (pai,paj)表示上一个节点的坐标，ch表示本次搜索的字符必须和ch字符相同。
    bool dfs(vector> &grid, vector> &vis, int i, int j, int pai, int paj, char ch) {
        // 边界条件判断
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != ch)
            return false;
        if (vis[i][j]) // 已访问过该节点，说明存在环
            return true;
        vis[i][j] = true; // 标记当前节点为已访问
        int dirs[4][2] = {{-1, 0},
                          {1,  0},
                          {0,  -1},
                          {0,  1}};// 方向数组
        for (auto &dir: dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x == pai && y == paj) // 跳过上一个节点（避免回退）
                continue;
            if (dfs(grid, vis, x, y, i, j, ch))// 上下左右四个方向只要有一个能找到环，则返回true
                return true;
        }
        return false;
    }