C++刷leetcode(130. 被围绕的区域)【递归】

糖逗

题目描述：

1. 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
   
2. 
   
3. [["a","b","c","e"],
   
4. ["s","f","c","s"],
   
5. ["a","d","e","e"]]
   
6. 
   
7. 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
    
14. 输出：true
    
15. 示例 2：
    
16. 
    
17. 输入：board = [["a","b"],["c","d"]], word = "abcd"
    
18. 输出：false
    
19. 提示：
    
20. 
    
21. 1 <= board.length <= 200
    
22. 1 <= board[i].length <= 200
    
23. 
    
24. 来源：力扣（LeetCode）
    
25. 链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
    
26. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <vector>
   
2. #include <iostream>
   
3. 
   
4. using namespace std;
   
5. 
   
6. 
   
7. 
   
8. void dfs(vector<vector<char> >& input, int i, int j){
   
9.         if(i < 0 || i >= input.size() || j < 0 || j >= input[0].size() || input[i][j] == '#' || input[i][j] == 'X') return;
   
10.         input[i][j] = '#';
    
11.         dfs(input, i - 1, j);
    
12.         dfs(input, i + 1, j);
    
13.         dfs(input, i, j+1);
    
14.         dfs(input, i, j-1);
    
15. }
    
16. 
    
17. void solution(vector<vector<char> >& input){
    
18.         if(input.size() == 0) return;
    
19.         int row = input.size();
    
20.         int col = input[0].size();
    
21.         for(int i = 0; i < row; i++){
    
22.                 for(int j = 0; j < col; j++){
    
23.                         bool temp = i==0 || j == 0 || i == row-1 || j == col -1;
    
24.                         if(temp && input[i][j] == 'O'){
    
25.                                 dfs(input, i, j);
    
26.                         }
    
27.                 }
    
28.         }
    
29.        
    
30.         for (int i = 0; i < row; i++) {
    
31.         for (int j = 0; j < col; j++) {
    
32.             if (input[i][j] == 'O') {
    
33.                 input[i][j] = 'X';
    
34.             }
    
35.             if (input[i][j] == '#') {
    
36.                 input[i][j] = 'O';
    
37.             }
    
38.         }
    
39.     }
    
40.        
    
41.        
    
42.        
    
43. }
    
44. 
    
45. int main(void){
    
46.         int row;
    
47.         vector<vector<char> > input;
    
48.         cout << "please send row for the vector:" << endl;
    
49.         cin >> row;
    
50.         cin.clear();
    
51.         cout << "send columns for the vector:" << endl;
    
52.         int col;
    
53.         cin >> col;
    
54.         cin.clear();
    
55.         input.resize(row);
    
56.         char temp;
    
57.         for(int i = 0 ; i < row; i++){
    
58.                 for(int j = 0; j < col; j++){
    
59.                         cin >> temp;
    
60.                         input[i].push_back(temp);
    
61.                 }
    
62.         }
    
63.         solution(input);
    
64.         for(int i = 0 ; i < row; i++){
    
65.                 for(int j = 0; j < col; j++){
    
66.                         cout << input[i][j] << " ";
    
67.                 }
    
68.                 cout << endl;
    
69.         }
    
70.        
    
71.         return 0;
    
72. }

复制代码

注意事项：
1.参考链接：https://leetcode-cn.com/problems ... -cha-ji-by-ac_pipe/

糖逗

相似的题：200. 岛屿数量

1. 
   
2. 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
   
3. 
   
4. 示例 1:
   
5. 
   
6. 输入:
   
7. 11110
   
8. 11010
   
9. 11000
   
10. 00000
    
11. 
    
12. 输出: 1
    
13. 示例 2:
    
14. 
    
15. 输入:
    
16. 11000
    
17. 11000
    
18. 00100
    
19. 00011
    
20. 
    
21. 输出: 3

复制代码

1. #include <vector>
   
2. #include <iostream>
   
3. 
   
4. using namespace std;
   
5. 
   
6. void dfs(vector<vector<char> > & input, int row, int col){
   
7.         if(row < 0 || row >= input.size() || col < 0 || col >= input[0].size() || input[row][col] == '0'){
   
8.                 return;
   
9.         }
   
10.         input[row][col] = '0';
    
11.        
    
12.         dfs(input, row + 1, col);
    
13.         dfs(input, row-1, col);
    
14.         dfs(input, row, col+1);
    
15.         dfs(input, row, col-1);
    
16. }
    
17. 
    
18. 
    
19. 
    
20. int solution(vector<vector<char> > & input){
    
21.         int res = 0;
    
22.         if(input.size() == 0) return res;
    
23.         for(int i = 0; i < input.size(); i++){
    
24.                 for(int j = 0; j < input[0].size(); j++){
    
25.                         if(input[i][j] == '1'){
    
26.                                 dfs(input, i, j);
    
27.                                 res++;
    
28.                         }
    
29.                 }
    
30.         }
    
31.     return res;
    
32. }
    
33. 
    
34. 
    
35. 
    
36. 
    
37. int main(void){
    
38.         int row;
    
39.     vector<vector<char> > input;
    
40.     cout << "please send row for the vector:" << endl;
    
41.     cin >> row;
    
42.     cin.clear();
    
43.     cout << "send columns for the vector:" << endl;
    
44.     int col;
    
45.     cin >> col;
    
46.     cin.clear();
    
47.     input.resize(row);
    
48.     char temp;
    
49.     for(int i = 0 ; i < row; i++){
    
50.         for(int j = 0; j < col; j++){
    
51.             cin >> temp;
    
52.             input[i].push_back(temp);
    
53.         }
    
54.     }
    
55.    
    
56.     int res = solution(input);
    
57.     cout << res << endl;
    
58.         return 0;
    
59. }

复制代码