西昌市做网站的公司,网站解析后怎么做,网站技能培训,全国十大数字展馆设计公司二维网格图中探测环 给你一个二维字符网格数组 grid #xff0c;大小为 m x n #xff0c;你需要检查 grid 中是否存在 相同值 形成的环。
一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子#xff0c;你可以移动到它上、下、左、右四个方…二维网格图中探测环 给你一个二维字符网格数组 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 解释如下图所示只有高亮所示的一个合法环
示例 3
输入grid [[“a”,“b”,“b”],[“b”,“z”,“b”],[“b”,“b”,“a”]] 输出false
提示
m grid.length n grid[i].length 1 m 500 1 n 500 grid 只包含小写英文字母。
分析看到题意就知道是个搜索题但如何判断环这是解决本题的核心问题。 其实仔细想想只要我下一个访问的节点并不是上一个节点并且和当前节点的字符相同不就符合环的定义吗并不需要一定是一个完整的环在搜索的半路找到了环就足以解题。 所以我们要记录下上一个节点不必判断是否回到了起点。 保存上一个节点可以把行列下表都记录下来还有一个方法就是把二维网格标号那么每个位置的标号不就唯一了唯一就可以判断是否是上一个点于是我们把x,y坐标转化成一个唯一标号就可以判断是否是上一个节点了。用唯一标识去判断上一个点的好处是减小了空间并能防止两个点判断相等时的错误比如我要判断这两个点是否相等x!x’y!y’对吗这里中间要用||才对只要一个参数不同就是不同的点了减小了犯逻辑错误的可能。这个题目还有一个陷阱就是关于如何剪枝的问题因为我们不可能对每一个节点都去搜索这样的搜索空间过于庞大而搜索过的字符一定dfs都已经搜索过根据图论如果一个图中存在环无论无门从哪个位置走一定能找到一个环所以这里我们尽可标记访问过的点就好连续的字符搜索一遍就够了不必恢复现场因为要剪枝。搜索过程中我只要保证不继续搜索上一个节点就可以了访问过的节点大可不必绕开走 本题刚开始想很好想但容易落入深搜的陷阱记录一下。
class Solution {
public:int book[510][510];int row,col,pre,dir[4][2] {{1,0},{-1,0},{0,1},{0,-1}};bool judge(int s,int e,int step,vectorvectorchar grid,int pre){if(book[s][e]step3)return 1;book[s][e]1;for(int i0;i4;i){int ts sdir[i][0];int te edir[i][1];if(te0ts0tsrowtecolgrid[s][e]grid[ts][te]pre!ts*rowte){if(judge(ts,te,step1,grid,s*rowe))return 1;}}return 0;}bool containsCycle(vectorvectorchar grid) {col grid[0].size();row grid.size();res0;for(int i0;irow!res;i){for(int j0;jcol!res;j){if(!book[i][j]judge(i,j,1,grid,-1))return 1;}}return 0;}
};
