总结：在写dfs时，要尽可能减少不必要的计算

题目链接,一道比较常规的搜索题目

1.被卡代码

class Solution {
public:
bool flag[505][505];
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,num;
/*
int find(int x){
    if(p[x]!=x)  p[x]=find(p[x]);
    return p[x];
}
*/
void dfs(int x,int y,vector<vector<int>> g){
    for(int i=0;i<4;++i){
        int xx=x+d[i][0],yy=y+d[i][1];
        if(xx>=0&&xx<n&&yy>=0&&yy<m&&!flag[xx][yy]&&g[xx][yy]==1){
            flag[xx][yy]=1;
            dfs(xx,yy,g);
        }
    }
}

    int numEnclaves(vector<vector<int>>& g){
    n=g.size(),m=g[0].size(),num=0;
    for(int i=0;i<n;++i)
       for(int j=0;j<m;++j)
        if((i==0||i==n-1||j==0||j==m-1)&&g[i][j]==1&&!flag[i][j])
        flag[i][j]=1,dfs(i,j,g);

    for(int i=1;i<n-1;++i)
       for(int j=1;j<m-1;++j)
       if(flag[i][j]==0&&g[i][j]==1)
       num++;

    return num;       
    }
};

2.通过代码

class Solution {
public:
int n,m,count;
void dfs(vector<vector<int>>& g,int i, int j) {
        if (!(i >= 0 && j >= 0 && i < n && j < m))
            return;
        if (g[i][j] == 1) {
            g[i][j] = -1;
        } 
        else return;

        dfs(g, i - 1, j);
        dfs(g, i + 1, j);
        dfs(g, i, j - 1);
        dfs(g, i, j + 1);
}

    int numEnclaves(vector<vector<int>>& g){
    n=g.size(),m=g[0].size(),count=0;
     for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if ((i == 0 || j == 0 || i == n - 1 || j == m - 1) && g[i][j] == 1)
                    dfs(g, i, j);

    for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == 1) 
                    count++;

        return count;  
    }
};