Advertisement
Josif_tepe

Untitled

Mar 18th, 2021
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include <iostream>
  2. #include<queue>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7. int n,m;
  8. cin>>n>>m;
  9. int mat[n][m];
  10. int s=2e9;
  11. int si,sj;
  12. int roboti=0;
  13. for(int i=0; i<n; i++)
  14. {
  15. for(int j=0; j<m; j++)
  16. {
  17. cin>>mat[i][j];
  18. }
  19. }
  20. queue<int>q;
  21.  
  22. bool visited[n][m];
  23. for(int i=0; i<n; i++)
  24. {
  25. for(int j=0; j<m; j++)
  26. {
  27. visited[i][j]=false;
  28. }
  29. }
  30. int di[]= {-1,1,0,0};
  31. int dj[]= {0,0,-1,1};
  32. for(int i=0; i<n; i++)
  33. {
  34. for(int j=0; j<m; j++)
  35. {
  36. si=-1;
  37. sj=-1;
  38. s=2e9;
  39. for(int x=0; x<n; x++)
  40. {
  41. for(int y=0; y<m; y++)
  42. {
  43. if(mat[x][y]<s && !visited[x][y])
  44. {
  45. s=mat[x][y];
  46. si=x;
  47. sj=y;
  48. }
  49. }
  50. }
  51. if(si!=-1 && sj!=-1)
  52. {
  53.         q.push(si);
  54.         q.push(sj);
  55. roboti+=1;
  56. visited[si][sj]=true;
  57. while(!q.empty())
  58. {
  59. int ci=q.front();
  60. q.pop();
  61. int cj=q.front();
  62. q.pop();
  63. for(int k=0; k<4; k++)
  64. {
  65. int ti=ci+di[k];
  66. int tj=cj+dj[k];
  67. if(ti>=0 && tj>=0 && ti<n && tj<m && !visited[ti][tj] && mat[ti][tj]>=mat[ci][cj])
  68. {
  69. visited[ti][tj]= true;
  70. q.push(ti);
  71. q.push(tj);
  72. }
  73. }
  74.  
  75. }
  76. }
  77. }
  78. }
  79. cout<<roboti;
  80.  
  81. return 0;
  82. }
  83.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement