Advertisement
Josif_tepe

Untitled

Mar 18th, 2021
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. #include <iostream>
  2. #include<queue>
  3. #include <fstream>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8. int n,m;
  9. cin>>n>>m;
  10. int w;
  11. cin>>w;
  12. char mat[n][m];
  13. pair<int,int>p[n*m + 1];
  14. int brojac=0;
  15. for(int i=0;i<n;i++)
  16. {
  17. for(int j=0;j<m;j++)
  18. {
  19. cin>>mat[i][j];
  20.  
  21. if(mat[i][j]=='C')
  22. {
  23.  
  24. p[brojac].first=i;
  25. p[brojac].second=j;
  26. brojac++;
  27. }
  28. }
  29. }
  30. bool visited[n][m];
  31. for(int i=0;i<n;i++)
  32. {
  33. for(int j=0;j<m;j++)
  34. {
  35. visited[i][j]=false;
  36. }
  37. }
  38. int preseci[n][m];
  39. for(int i=0;i<n;i++)
  40. {
  41. for(int j=0;j<m;j++)
  42. {
  43. preseci[i][j]=0;
  44. }
  45. }
  46. queue<int>q;
  47. int di[]={-1,1,0,0};
  48. int dj[]={0,0,-1,1};
  49. for(int i=0;i<brojac;i++)
  50. {
  51.     q.push(p[i].first);
  52.     q.push(p[i].second);
  53. q.push(0);
  54. visited[p[i].first][p[i].second]=true;
  55. while(!q.empty())
  56. {
  57. int ci=q.front();
  58. q.pop();
  59. int cj=q.front();
  60. q.pop();
  61. int br=q.front();
  62. q.pop();
  63.  
  64. for(int k=0;k<4;k++)
  65. {
  66. int ti=ci+di[k];
  67. int tj=cj+dj[k];
  68. if(ti>=0 && ti<n && tj>=0 && tj<m && mat[ti][tj]!='#' && !visited[ti][tj]  && br+1<=w)
  69. {
  70. preseci[ti][tj]++;
  71. q.push(ti);
  72. q.push(tj);
  73. visited[ti][tj]=true;
  74. q.push(br+1);
  75. }
  76. }
  77.  
  78. }
  79. for(int r=0;r<n;r++)
  80. {
  81. for(int j=0;j<m;j++)
  82. {
  83. visited[r][j]=false;
  84. }
  85. }
  86.  
  87.  
  88. }
  89. int maks=-2e9;
  90. int maks_i;
  91. int maks_j;
  92. for(int i=0;i<n;i++)
  93. {
  94. for(int j=0;j<m;j++)
  95. {
  96. if(preseci[i][j]>maks and mat[i][j] == '.')
  97. {
  98. maks=preseci[i][j];
  99. maks_i=i;
  100. maks_j=j;
  101. }
  102. }
  103. }
  104. cout<<maks_i+1<<" "<<maks_j+1;
  105. return 0;
  106. }
  107.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement