5482. 二维网格图中探测环

5482. 二维网格图中探测环

我用了fx，fy来记录来的坐标，y总用了i ^ 1来判断是不是来的方向，tql%%

我：

class Solution {
public:
    int n,m;
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    vector<vector<bool>>vis;
    vector<vector<char>> grid;
    
    bool dfs(int x,int y,int fx,int fy,int len){
        vis[x][y]=true;
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a>=0 && a<n && b>=0 && b<m && grid[a][b]==grid[x][y]){
                if(a==fx && b==fy)continue;
                if(vis[a][b] && len>=4)return true;
                else if(dfs(a,b,x,y,len+1))return true;
            }
        }
        return false;
    }
    
    bool containsCycle(vector<vector<char>>& _grid) {
        grid=_grid;

        n=grid.size();
        m=grid[0].size();
        
        
        vis=vector<vector<bool>>(n,vector<bool>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!vis[i][j] && dfs(i,j,-1,-1,0))return true;
            }
        }
        return false;
    }
};

yxc

class Solution {
public:
    vector<vector<char>> g;
    vector<vector<bool>> st;

    bool containsCycle(vector<vector<char>>& grid) {
        g = grid;
        st = vector<vector<bool>>(g.size(), vector<bool>(g[0].size()));
        for (int i = 0; i < g.size(); i ++ )
            for (int j = 0; j < g[0].size(); j ++ )
                if (!st[i][j] && dfs(i, j,  -1))
                    return true;
        return false;
    }

    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    bool dfs(int x, int y, int p) {
        st[x][y] = true;
        for (int i = 0; i < 4; i ++ )
            if (i != p) {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < g.size() && b >= 0 && b < g[0].size() && g[x][y] == g[a][b]) {
                    if (st[a][b]) return true;
                    if (dfs(a, b, i ^ 1)) return true;
                }
            }
        return false;
    }
};