Advertisement
yoyoboyss

Untitled

Feb 14th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.99 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int NMAX = 105;
  5.  
  6. ifstream fin("insule.in");
  7. ofstream fout("insule.out");
  8.  
  9. int dx[4] = {0, 0, -1, 1};
  10. int dy[4] = {-1, 1, 0, 0};
  11. queue < pair <int, int> > Q;
  12.  
  13. int H[NMAX][NMAX], Par[NMAX][NMAX];
  14.  
  15. int M, N;
  16. int nr_insule[4], nr, Lg=INT_MAX;
  17.  
  18. void afisare_matrice(int matrice[NMAX][NMAX]){
  19. fout << endl;
  20. for(int i=0; i<N; i++){
  21. for(int j=0; j<M; j++){
  22. fout << matrice[i][j];
  23. if(matrice[i][j]>=10 || matrice[i][j]<0)
  24. fout << ' ';
  25. else
  26. fout << " ";
  27. }
  28. fout << endl;
  29. }
  30. }
  31.  
  32. int read(){
  33. fin >> N >> M;
  34. for(int i = 0; i < N; i++)
  35. for(int j = 0; j < M; j++){
  36. char c;
  37. fin >> c;
  38. H[i][j] = c - '0';
  39. }
  40. }
  41.  
  42. bool OK(int i, int j){
  43. if( i < 0 || j < 0 || i > N-1 || j > M-1)
  44. return false;
  45. return true;
  46. }
  47.  
  48. int fil(int x, int y){
  49. Par[x][y]=nr;
  50. for(int d = 0; d < 4; d++){
  51. int i_1 = x + dx[d];
  52. int j_1 = y + dy[d];
  53. if(OK(i_1, j_1) && !Par[i_1][j_1] && H[i_1][j_1] && H[x][y]==H[i_1][j_1]){
  54. Par[i_1][j_1]=nr;
  55. fil(i_1, j_1);
  56. }
  57. }
  58. }
  59.  
  60. int l_0(int matrice[NMAX][NMAX]){
  61. for(int i=0; i < N; i++)
  62. for(int j = 0; j < N; j++)
  63. matrice[i][j]=0;
  64. }
  65.  
  66. int ok(int i, int j){
  67. for(int d = 0; d < 4; d++){
  68. int i_1 = i + dx[d];
  69. int j_1 = j + dy[d];
  70. if(OK(i_1, j_1) && H[i_1][j_1]==0)
  71. return true;
  72. }
  73. return false;
  74. }
  75.  
  76. int lee(int x, int y){
  77. int Lee[NMAX][NMAX];
  78. l_0(Lee);
  79. Lee[x][y]=0;
  80. Q.push(make_pair(x, y));
  81. cout << ok(x, y) << ' ';
  82. if(ok(x, y)){
  83. while(!Q.empty()){
  84. int i = Q.front().first;
  85. int j = Q.front().second;
  86. for(int d = 0; d < 4; d++){
  87. int i_1 = i + dx[d];
  88. int j_1 = j + dy[d];
  89. if(OK(i_1, j_1) && H[i_1][j_1] != 3 && H[i_1][j_1] != 1){
  90. if(!Lee[i_1][j_1] || Lee[i_1][j_1]>Lee[i][j]+1){
  91. Lee[i_1][j_1]=Lee[i][j]+1;
  92. Q.push(make_pair(i_1, j_1));
  93. if(H[i_1][j_1] == 2 && Lee[i_1][j_1]!=1){
  94. Lg=min(Lg, Lee[i_1][j_1]-1);
  95. }
  96. }
  97. }
  98. }
  99. Q.pop();
  100. }
  101. }
  102. //if(x == 34 && y == 99)
  103. //afisare_matrice(Lee);
  104. Lee[x][y]=0;
  105. }
  106.  
  107. int main(){
  108. read();
  109. for(int i = 0; i < N; i++){
  110. for(int j = 0; j < M; j++){
  111. if(H[i][j]==1){
  112. lee(i, j);
  113. }
  114. if(!Par[i][j] && H[i][j]){
  115. nr++;
  116. fil(i, j);
  117. nr_insule[H[i][j]]++;
  118. }
  119. }
  120. cout << endl;
  121. }
  122. for(int i = 1; i < 4; i++){
  123. fout << nr_insule[i] << ' ';
  124. }
  125. fout << Lg;
  126. return 0;
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement