鱼C论坛

 找回密码
 立即注册
查看: 1597|回复: 1

[技术交流] C++刷leetcode(130. 被围绕的区域)【递归】

[复制链接]
发表于 2020-4-8 16:24:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 糖逗 于 2020-5-8 17:36 编辑

题目描述:
  1. 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

  2. [["a","b","c","e"],
  3. ["s","f","c","s"],
  4. ["a","d","e","e"]]

  5. 但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

  6.  

  7. 示例 1:

  8. 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
  9. 输出:true
  10. 示例 2:

  11. 输入:board = [["a","b"],["c","d"]], word = "abcd"
  12. 输出:false
  13. 提示:

  14. 1 <= board.length <= 200
  15. 1 <= board[i].length <= 200

  16. 来源:力扣(LeetCode)
  17. 链接:https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
  18. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码



  1. #include <vector>
  2. #include <iostream>

  3. using namespace std;



  4. void dfs(vector<vector<char> >& input, int i, int j){
  5.         if(i < 0 || i >= input.size() || j < 0 || j >= input[0].size() || input[i][j] == '#' || input[i][j] == 'X') return;
  6.         input[i][j] = '#';
  7.         dfs(input, i - 1, j);
  8.         dfs(input, i + 1, j);
  9.         dfs(input, i, j+1);
  10.         dfs(input, i, j-1);
  11. }

  12. void solution(vector<vector<char> >& input){
  13.         if(input.size() == 0) return;
  14.         int row = input.size();
  15.         int col = input[0].size();
  16.         for(int i = 0; i < row; i++){
  17.                 for(int j = 0; j < col; j++){
  18.                         bool temp = i==0 || j == 0 || i == row-1 || j == col -1;
  19.                         if(temp && input[i][j] == 'O'){
  20.                                 dfs(input, i, j);
  21.                         }
  22.                 }
  23.         }
  24.        
  25.         for (int i = 0; i < row; i++) {
  26.         for (int j = 0; j < col; j++) {
  27.             if (input[i][j] == 'O') {
  28.                 input[i][j] = 'X';
  29.             }
  30.             if (input[i][j] == '#') {
  31.                 input[i][j] = 'O';
  32.             }
  33.         }
  34.     }
  35.        
  36.        
  37.        
  38. }

  39. int main(void){
  40.         int row;
  41.         vector<vector<char> > input;
  42.         cout << "please send row for the vector:" << endl;
  43.         cin >> row;
  44.         cin.clear();
  45.         cout << "send columns for the vector:" << endl;
  46.         int col;
  47.         cin >> col;
  48.         cin.clear();
  49.         input.resize(row);
  50.         char temp;
  51.         for(int i = 0 ; i < row; i++){
  52.                 for(int j = 0; j < col; j++){
  53.                         cin >> temp;
  54.                         input[i].push_back(temp);
  55.                 }
  56.         }
  57.         solution(input);
  58.         for(int i = 0 ; i < row; i++){
  59.                 for(int j = 0; j < col; j++){
  60.                         cout << input[i][j] << " ";
  61.                 }
  62.                 cout << endl;
  63.         }
  64.        
  65.         return 0;
  66. }
复制代码




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

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-4-9 11:29:57 | 显示全部楼层
相似的题:200. 岛屿数量

  1. 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

  2. 示例 1:

  3. 输入:
  4. 11110
  5. 11010
  6. 11000
  7. 00000

  8. 输出: 1
  9. 示例 2:

  10. 输入:
  11. 11000
  12. 11000
  13. 00100
  14. 00011

  15. 输出: 3
复制代码


  1. #include <vector>
  2. #include <iostream>

  3. using namespace std;

  4. void dfs(vector<vector<char> > & input, int row, int col){
  5.         if(row < 0 || row >= input.size() || col < 0 || col >= input[0].size() || input[row][col] == '0'){
  6.                 return;
  7.         }
  8.         input[row][col] = '0';
  9.        
  10.         dfs(input, row + 1, col);
  11.         dfs(input, row-1, col);
  12.         dfs(input, row, col+1);
  13.         dfs(input, row, col-1);
  14. }



  15. int solution(vector<vector<char> > & input){
  16.         int res = 0;
  17.         if(input.size() == 0) return res;
  18.         for(int i = 0; i < input.size(); i++){
  19.                 for(int j = 0; j < input[0].size(); j++){
  20.                         if(input[i][j] == '1'){
  21.                                 dfs(input, i, j);
  22.                                 res++;
  23.                         }
  24.                 }
  25.         }
  26.     return res;
  27. }




  28. int main(void){
  29.         int row;
  30.     vector<vector<char> > input;
  31.     cout << "please send row for the vector:" << endl;
  32.     cin >> row;
  33.     cin.clear();
  34.     cout << "send columns for the vector:" << endl;
  35.     int col;
  36.     cin >> col;
  37.     cin.clear();
  38.     input.resize(row);
  39.     char temp;
  40.     for(int i = 0 ; i < row; i++){
  41.         for(int j = 0; j < col; j++){
  42.             cin >> temp;
  43.             input[i].push_back(temp);
  44.         }
  45.     }
  46.    
  47.     int res = solution(input);
  48.     cout << res << endl;
  49.         return 0;
  50. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-16 04:13

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表