当前位置:   article > 正文

LeetCode 419. 甲板上的战舰(C、C++、python)_c++ 军舰

c++ 军舰

给定一个二维的甲板, 请计算其中有多少艘战舰。 战舰用 'X'表示,空位用 '.'表示。 你需要遵守以下规则:

  • 给你一个有效的甲板,仅由战舰或者空位组成。
  • 战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成,或者 Nx1 (N 行, 1 列)组成,其中N可以是任意大小。
  • 两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。

示例 :

  1. X..X
  2. ...X
  3. ...X

在上面的甲板中有2艘战舰。

无效样例 :

  1. ...X
  2. XXXX
  3. ...X

你不会收到这样的无效甲板 - 因为战舰之间至少会有一个空位将它们分开。

进阶:

你可以用一次扫描算法,只使用O(1)额外空间,并且不修改甲板的值来解决这个问题吗?

C

  1. void DFS(char** board,int row, int col,int m,int n)
  2. {
  3. if(row-1>=0 && 'X'==board[row-1][col])
  4. {
  5. board[row-1][col]='a';
  6. DFS(board,row-1,col,m,n);
  7. }
  8. if(row+1<m && 'X'==board[row+1][col])
  9. {
  10. board[row+1][col]='a';
  11. DFS(board,row+1,col,m,n);
  12. }
  13. if(col-1>=0 && 'X'==board[row][col-1])
  14. {
  15. board[row][col-1]='a';
  16. DFS(board,row,col-1,m,n);
  17. }
  18. if(col+1<n && 'X'==board[row][col+1])
  19. {
  20. board[row][col+1]='a';
  21. DFS(board,row,col+1,m,n);
  22. }
  23. }
  24. int countBattleships(char** board, int boardRowSize, int boardColSize)
  25. {
  26. int m=boardRowSize;
  27. int n=boardColSize;
  28. int sum=0;
  29. for(int i=0;i<m;i++)
  30. {
  31. for(int j=0;j<n;j++)
  32. {
  33. if('X'==board[i][j])
  34. {
  35. board[i][j]='a';
  36. sum++;
  37. DFS(board,i,j,m,n);
  38. }
  39. }
  40. }
  41. return sum;
  42. }

C++ 法一

  1. class Solution {
  2. public:
  3. void DFS(vector<vector<char>>& board,int row,int col)
  4. {
  5. if(row-1>=0 && 'X'==board[row-1][col])
  6. {
  7. board[row-1][col]='a';
  8. DFS(board,row-1,col);
  9. }
  10. if(row+1<board.size() && 'X'==board[row+1][col])
  11. {
  12. board[row+1][col]='a';
  13. DFS(board,row+1,col);
  14. }
  15. if(col-1>=0 && 'X'==board[row][col-1])
  16. {
  17. board[row][col-1]='a';
  18. DFS(board,row,col-1);
  19. }
  20. if(col+1<board[0].size() && 'X'==board[row][col+1])
  21. {
  22. board[row][col+1]='a';
  23. DFS(board,row,col+1);
  24. }
  25. }
  26. int countBattleships(vector<vector<char>>& board)
  27. {
  28. int m=board.size();
  29. int n=board[0].size();
  30. int sum=0;
  31. for(int i=0;i<m;i++)
  32. {
  33. for(int j=0;j<n;j++)
  34. {
  35. if('X'==board[i][j])
  36. {
  37. board[i][j]='a';
  38. sum++;
  39. DFS(board,i,j);
  40. }
  41. }
  42. }
  43. return sum;
  44. }
  45. };

C++法二

  1. class Solution {
  2. public:
  3. int countBattleships(vector<vector<char>>& board)
  4. {
  5. int m=board.size();
  6. int n=board[0].size();
  7. int sum=0;
  8. for(int i=0;i<m;i++)
  9. {
  10. for(int j=0;j<n;j++)
  11. {
  12. if('X'==board[i][j] && (0==i || '.'==board[i-1][j]))
  13. {
  14. sum++;
  15. j++;
  16. while('X'==board[i][j])
  17. {
  18. j++;
  19. }
  20. }
  21. }
  22. }
  23. return sum;
  24. }
  25. };

python法一

  1. class Solution:
  2. def DFS(self, board, row, col):
  3. if row-1>=0 and 'X'==board[row-1][col]:
  4. board[row-1][col]='a'
  5. self.DFS(board,row-1,col)
  6. if row+1<len(board) and 'X'==board[row+1][col]:
  7. board[row+1][col]='a'
  8. self.DFS(board,row+1,col)
  9. if col-1>=0 and 'X'==board[row][col-1]:
  10. board[row][col-1]='a'
  11. self.DFS(board,row,col-1)
  12. if col+1<len(board[0]) and 'X'==board[row][col+1]:
  13. board[row][col+1]='a'
  14. self.DFS(board,row,col+1)
  15. def countBattleships(self, board):
  16. """
  17. :type board: List[List[str]]
  18. :rtype: int
  19. """
  20. m=len(board)
  21. n=len(board[0])
  22. res=0
  23. for i in range(m):
  24. for j in range(n):
  25. if 'X'==board[i][j]:
  26. res+=1
  27. board[i][j]='a'
  28. self.DFS(board,i,j)
  29. return res

python法二

  1. class Solution:
  2. def countBattleships(self, board):
  3. """
  4. :type board: List[List[str]]
  5. :rtype: int
  6. """
  7. m=len(board)
  8. n=len(board[0])
  9. res=0
  10. for i in range(m):
  11. for j in range(n):
  12. if 'X'==board[i][j] and (0==i or '.'==board[i-1][j]) and (0==j or '.'==board[i][j-1]):
  13. res+=1
  14. return res

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/718449
推荐阅读
相关标签
  

闽ICP备14008679号