Advertisement
Singasking

Untitled

Jul 4th, 2023
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.20 KB | None | 0 0
  1. class Solution {
  2. public:
  3. void dfs(int r,int c, vector<vector<int>>& visited,vector<vector<int>>& stones) {
  4. if(visited[r][c]) return;
  5. visited[r][c]=1;
  6. for(int cn=0;cn<stones[r].size();cn++){
  7. if(visited[r][cn]==0) {
  8. dfs(r,cn,visited,stones);
  9. }
  10. }
  11. for(int rn=0;rn<stones.size();rn++){
  12. if(visited[rn][c]==0) {
  13. dfs(rn,c,visited,stones);
  14. }
  15. }
  16. }
  17.  
  18. int removeStones(vector<vector<int>>& stones) {
  19. int count=0;
  20. int mRow=0;
  21. int mCol=0;
  22.  
  23. for(auto stone:stones) { mRow = max(mRow,stone[0]);
  24.  
  25. mCol = max(mCol,stone[1]);
  26. }
  27. vector<vector<int>> visited(mRow+1,vector<int>(mCol+1,0));
  28. vector<vector<int>> stonex(mRow+1,vector<int>(mCol+,0));
  29. for(auto stone:stones){ stonex[stone[0]][stone[1]]=1;}
  30. for(int r=0;r<stonex.size();r++) {
  31. for(int c=0;c<stonex[r].size();c++) {
  32. if(visited[r][c]==0) {
  33. dfs(r,c,visited,stonex);
  34. count++;
  35. }
  36. }
  37.  
  38. }
  39. return stones.size()-count;
  40. }
  41. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement