leetcode 1559. 二维网格图中探测环-Detect Cycles in 2D Grid

Problem: 1559. 二维网格图中探测环-Detect Cycles in 2D Grid

深度优先搜索，不能访问前一个坐标，不能重复访问状态数组status，字符相同，若字符相同且不是上一个坐标且之前访问过，那么就是一个满足条件的环，可以返回true的

Code

class Solution { public: vector<vector<bool>> status; int n, m, dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; bool flag = false; void dfs(int x, int y, vector<vector<char>>& grid, char ch, int preX, int preY) { if(flag) return; int zx, zy; for(int i = 0; i < 4; i++) { zx = x + dir[i][0]; zy = y + dir[i][1]; if(zx>=0 && zx < m && zy>=0 && zy < n && (zx!=preX || zy!=preY) && grid[zx][zy]==ch) { if( status[zx][zy] == true ) { flag = true; return; } else { status[zx][zy] = true; dfs(zx, zy, grid, ch, x, y); } } } } bool containsCycle(vector<vector<char>>& grid) { m = grid.size(), n = grid[0].size(); status.assign(m, vector<bool>(n, false)); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(status[i][j] == false) { status[i][j] = true; dfs(i, j, grid, grid[i][j], i, j); if(flag) return true; } } } return false; } };