Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2019
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. ifstream fin("wow.in");
  7. ofstream fout("wow.out");
  8.  
  9. int n, p, m, a[102][102], s[102][102], b[102][102];
  10. int dx[5] = {0, -1, 0, 1, 0};
  11. int dy[5] = {0, 0, 1, 0, -1};
  12.  
  13. /*
  14. a - matricea mea initiala
  15. b - pe matricea b fac lee-ul
  16. s - suprapun lee-ul fiecarei pereche (x,y)
  17.  
  18. Init() - pentru o noua pereche (x,y) matricea b ia valorile matricei a
  19. lee() - prelucreaza atat b-ul cat si s-ul
  20. Minim() - determin punctul minim in care se intalnesc perechile (x, y)
  21. */
  22.  
  23. void Init()
  24. {
  25. int i, j;
  26. for(i = 0; i < n; i++)
  27. for(j = 0; j < p; j++)
  28. b[i][j] = a[i][j];
  29. }
  30.  
  31. void Lee(int x, int y)
  32. {
  33. int pr, ul, x_curent, y_curent, x_vecin, y_vecin, i, j;
  34. int cx[100003], cy[100003];
  35. pr = ul = 1;
  36. cx[1] = x; cy[1] = y;
  37. Init();
  38. b[x][y] = 1;
  39. while(pr <= ul)
  40. {
  41. x_curent = cx[pr];
  42. y_curent = cy[pr];
  43. for(i = 1; i <= 4; i++)
  44. {
  45. x_vecin = x_curent + dx[i];
  46. y_vecin = y_curent + dy[i];
  47. if(x_vecin >= 0 && x_vecin < n && y_vecin >= 0 && y_vecin < p && b[x_vecin][y_vecin] == 0)
  48. {
  49. ul++;
  50. cx[ul] = x_vecin;
  51. cy[ul] = y_vecin;
  52. b[x_vecin][y_vecin] = b[x_curent][y_curent] + 1;
  53. }
  54. }
  55. pr++;
  56. }
  57. for(i = 0; i < n; i++)
  58. for(j = 0; j < p; j++)
  59. if(a[i][j] != 1) s[i][j] = s[i][j] + b[i][j];
  60. }
  61.  
  62. void Minim()
  63. {
  64. int i, j, M = 2000000000, x, y;
  65. for(i = 0; i < n; i++)
  66. for(j = 0; j < p; j++)
  67. if(s[i][j] < M && a[i][j] != 1)
  68. {
  69. x = i;
  70. y = j;
  71. M = s[i][j];
  72. }
  73.  
  74. fout << s[x][y] - m << "\n";
  75. fout << x << " " << y;
  76. }
  77.  
  78. int main()
  79. {
  80. int i, x, y, j;
  81. fin >> n >> p >> m;
  82. for(i = 0; i < n; i++)
  83. for(j = 0; j < p; j++)
  84. fin >> a[i][j];
  85. for(i = 1; i <= m; i++)
  86. {
  87. fin >> x >> y;
  88. Lee(x, y);
  89. }
  90. Minim();
  91.  
  92. return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement