Leetcode DFS 1020. 飞地的数量

约定不等于承诺〃 2023-03-14 08:19 8阅读 0赞

### Leetcode DFS 1020. 飞地的数量 ###

*  1、问题分析
 *  2、问题解决
 *  3、总结

# 1、问题分析 #

具体思路是从边界出发标记连通块，标记完成后，如果中心节点有值为1，但是仍然未被标记的说明是无法访问的节点，即题目的答案。

# 2、问题解决 #

笔者以C++方式解决。

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "math.h"
    #include "queue"
    
    struct TreeNode { 
    	int val;
    	TreeNode *left;
    	TreeNode *right;
    
    	TreeNode(int x) : val(x), left(NULL), right(NULL) { 
    
    	}
    };
    
    class Solution { 
    public:
    	// 设置上下左右访问点
    	int X[4] = {  0, 0, 1, -1 };
    	int Y[4] = {  1, -1, 0, 0 };
    	// 设置数组大小
    	static const int maxn = 501;
    	// 标记某个节点是否访问过
    	int visited[maxn][maxn] = {  false };
    	// 全局二维数组节点
    	vector<vector<int>> value;
    	// 二维数组长和宽
    	int m, n;
    	//节点结构体
    	struct node { 
    		int x, y;
    	} Node;
    	// 打印访问节点，调试使用
    	void print() { 
    		cout << "--------------------> chen--------------------------" << endl;
    		for (int i = 0; i < value.size(); ++i) { 
    			for (int j = 0; j < value[0].size(); ++j) { 
    				cout << visited[i][j] << " ";
    			}
    			cout << endl;
    		}
    	}
    
    	/** * 判断某个节点(x,y)是否需要访问 * @param x * @param y * @return */
    	bool judge(int x, int y) { 
    		// 越界则不访问
    		if (x < 0 || x >= m || y < 0 || y >= n) { 
    			return false;
    		}
    
    		// 访问过或是0节点不访问
    		return !(visited[x][y] != 0 || value[x][y] == 0);
    
    	}
    
    	/** * 其实这是深搜，将连通块节点的 visited 标记成 true * @param x * @param y */
    	void bfs(int x, int y) { 
    		queue<node> queueNode;
    		Node.x = x;
    		Node.y = y;
    		queueNode.push(Node);
    		visited[x][y] = true;
    		while (!queueNode.empty()) { 
    			// 取出头结点
    			node nodeFront = queueNode.front();
    			queueNode.pop();
    
    			// 在取出的头结点上下左右移动
    			for (int i = 0; i < 4; ++i) { 
    				int newX = nodeFront.x + X[i];
    				int newY = nodeFront.y + Y[i];
    
    				if (judge(newX, newY)) { 
    					bfs(newX, newY);
    				}
    			}
    		}
    	}
    
    	/** * 具体思路是从边界出发标记连通块，标记完成后，如果中心节点有值为1，但是仍然未被标记的 * 说明是无法访问的节点，即题目的答案 * @param A * @return */
    	int numEnclaves(vector<vector<int>> &A) { 
    		int ans = 0;
    		value = A;
    
    		m = A.size();
    		n = A[0].size();
    
    		// 此代码块的作用是从边界出发标记连通块
    		{ 
    			// 矩阵上下两层开始标记
    			for (int i = 0; i < n; ++i) { 
    				if (A[0][i] == 1 && visited[0][i] == 0) { 
    					bfs(0, i);
    				}
    
    				if (A[m - 1][i] == 1 && visited[m - 1][i] == 0) { 
    					bfs(m - 1, i);
    				}
    
    			}
    
    			// 矩阵左右两层开始标记
    			for (int i = 0; i < m; ++i) { 
    				if (A[i][0] == 1 && visited[i][0] == 0) { 
    					bfs(i, 0);
    				}
    
    				if (A[i][n - 1] == 1 && visited[i][n - 1] == 0) { 
    					bfs(i, n - 1);
    				}
    			}
    		}
    
    
    		for (int i = 0; i < m; ++i) { 
    			for (int j = 0; j < n; ++j) { 
    				if (A[i][j] == 1 && visited[i][j] == 0) { 
    					ans++;
    				}
    			}
    		}
    
    		return ans;
    	}
    };
    
    /** * 先序遍历 * @param root */
    void preorder(TreeNode *root) { 
    	if (root == NULL || root->val == -1) { 
    		return;
    	}
    	// 先访问根节点
    	cout << root->val << endl;
    	// 再访问左子节点
    	preorder(root->left);
    	// 最后访问右子节点
    	preorder(root->right);
    }
    
    /** * 根据数组创建二叉树 * @param a * @param n * @return */
    TreeNode *create(int a[], int n) { 
    	// 根据数组大小分配内存空间
    	TreeNode *ptree = (TreeNode *)malloc(sizeof(TreeNode) * n);
    	int i;
    	// 根据数组的值，依次给二叉树节点赋值
    	for (i = 0; i < n; i++) { 
    		// if (a[i] == -1) { 
    		// ptree[i] = NULL;
    		// continue;
    		// }
    		ptree[i].val = a[i];//数组a只起到一个赋值的作用
    		ptree[i].left = NULL;
    		ptree[i].right = NULL;
    	}
    	// 将数组中节点按照二叉树规则连接起来
    	for (i = 0; i <= n / 2 - 1; i++)//原来的父亲节点范围为1~n/2,现在0~n/2-1,所以注意n/2要取到等
    	{ 
    		if (2 * i + 1 <= n - 1)
    			ptree[i].left = &ptree[2 * i + 1];//把第2*i+1个结点的地址赋给左孩子
    		if (2 * i + 2 <= n - 1)
    			ptree[i].right = &ptree[2 * i + 2];
    	}
    	return ptree;
    }
    
    template<class T>
    
    /** * 获取数组长度 * @tparam T * @param array * @return */
    int getsize(T &array) { 
    	return sizeof(array) / sizeof(array[0]);
    }
    
    
    int main() { 
    	// int a[] = {5, 1, 4, -1, -1, 3, 6};
    	// int a[] = {2,1,3};
    	// int a[] = {10, 5, 15, -1, -1, 6, 20};
    	// int a[] = {5, 3, 6, 2, 4, -1, -1, 1};
    	// vector<vector<int>> A = { {0, 0, 0, 0},
    	// {1, 0, 1, 0},
    	// {0, 1, 1, 0},
    	// {0, 0, 0, 0}};
    
    	vector<vector<int>> A = {  {  0, 1, 1, 0 },
    	{  0, 0, 1, 0 },
    	{  0, 0, 1, 0 },
    	{  0, 0, 0, 0 } };
    
    	// 创建二叉树
    	// TreeNode *pNode = create(a, getsize(a));
    	// preorder(pNode);
    	Solution *pSolution = new Solution;
    	int i = pSolution->numEnclaves(A);
    	cout << i << endl;
    
    
    	system("pause");
    	return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]

有点菜，有时间再优化一下。

# 3、总结 #

书上的代码直接运行绝大部分是对的，但是总有一些软件的更新使得作者无能为力。之前的API是对的，但是之后就废弃了或修改了是常有的事。所以我们需要跟踪源代码。这只是一个小小的问题，如果没有前辈的无私奉献，很难想象我们自己一天能学到多少内容。感谢各位前辈的辛勤付出，让我们少走了很多的弯路！

点个赞再走呗！欢迎留言哦！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]: /images/20230312/f503f2e819e743338170b27d5da95371.png