In a generic DFS problem, we look for a starting point and from there we look for an end target position to reach.
Similarly, In the matrix-related problems, we look for any cell as a starting point and from there we look for any end target position by following the conditions of given problem statement.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// //Yellow Coding // DFS Template void dfs(vector<vector<int>>& matrix,int n,int m,int x,int y){ // 1. validity check // e.g. boundary check and additonal condition check such as compare values between cells if (!isvalid()) return; // 2. update cell // if the update depends on the values from neighbors, this step becomes the step 3 matrix[row][col]='#'; // 3. traverse to all neighbors // Blindly traverse to all neighbors since the boundary check is guaranteed in step 1 dfs(matrix, row - 1, col); dfs(matrix, row + 1, col); dfs(matrix, row, col - 1); dfs(matrix, row, col + 1); } int main(vector<vector<int>>& matrix) { for (int row : rows) { for (int col : cols) { // call dfs dfs(matrix, row, col); } } } |
Similar Problems:
Some DFS questions that you could try with the template to have a better understanding : ( with increasing difficulty )
