Advertisement
Guest User

Untitled

a guest
Nov 19th, 2019
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.27 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. struct Node{
  9. int data;
  10. Node*next;
  11. Node(int data){
  12. this->data=data;
  13. next=NULL;
  14. }
  15. };
  16.  
  17. class Queue{
  18. private:
  19. Node*head,*tail;
  20. int size;
  21. public:
  22. Queue(){
  23. head=NULL;
  24. tail=NULL;
  25. size=0;
  26. }
  27. void enqueue(int value){
  28. Node*temp=new Node(value);
  29. if(head==NULL){
  30. head=temp;
  31. tail=temp;
  32. size++;
  33. return;
  34. }
  35. tail->next=temp;
  36. tail=temp;
  37. size++;
  38. }
  39. void dequeue(){
  40. if(head==NULL){
  41. return;
  42. }
  43. head=head->next;
  44. }
  45. int getX(){
  46. return head->data;
  47. }
  48. int getY(){
  49. return head->next->data;
  50. }
  51. int getSize(){
  52. return size;
  53. }
  54. bool isEmpty() {
  55. return head == NULL;
  56. }
  57. };
  58.  
  59. int main() {
  60.  
  61. int N, M, T;
  62. cin >> N >> M >> T;
  63. if (N<1||M<1||T < 1)
  64. return 0;
  65.  
  66. Queue q;
  67. Queue helper;
  68. int xCoord, yCoord;
  69.  
  70.  
  71. int**matrix = new int*[N];
  72. for (int i = 0; i < N; i++) {
  73. matrix[i] = new int[M];
  74. }
  75.  
  76. for (int i = 0; i < N; i++) {
  77. for (int j = 0; j < M; j++) {
  78. matrix[i][j] = -1;
  79. }
  80. }
  81. while (cin >> xCoord >> yCoord) {
  82. if (xCoord > N || yCoord > M)
  83. continue;
  84. q.enqueue(N - xCoord);
  85. q.enqueue(yCoord - 1);
  86. matrix[N - xCoord][yCoord - 1] = 0;
  87. }
  88. for (int i = 0; i < T; i++) {
  89. while (!q.isEmpty()) {
  90. //At this point we check wether the apples
  91. //around the current one can be infected
  92. if (q.getX()+1<N&&matrix[q.getX() + 1][q.getY()] == -1) {
  93. matrix[q.getX() + 1][q.getY()] = i;
  94. helper.enqueue(q.getX() + 1);
  95. helper.enqueue(q.getY());
  96. }
  97. if (q.getX()-1>=0&&matrix[q.getX() - 1][q.getY()] == -1) {
  98. matrix[q.getX() - 1][q.getY()] = i;
  99. helper.enqueue(q.getX() - 1);
  100. helper.enqueue(q.getY());
  101. }
  102. if (q.getY()+1<M&&matrix[q.getX()][q.getY() + 1] == -1) {
  103. matrix[q.getX()][q.getY() + 1] = i;
  104. helper.enqueue(q.getX());
  105. helper.enqueue(q.getY() + 1);
  106. }
  107. if (q.getY()-1>=0&&matrix[q.getX()][q.getY() - 1] == -1) {
  108. matrix[q.getX()][q.getY() - 1] = i;
  109. helper.enqueue(q.getX());
  110. helper.enqueue(q.getY() - 1);
  111. }
  112. q.dequeue();
  113. q.dequeue();
  114. }
  115. while (!helper.isEmpty()) {
  116. //At this point the newly rotten are added
  117. q.enqueue(helper.getX());
  118. q.enqueue(helper.getY());
  119. helper.dequeue();
  120. helper.dequeue();
  121. }
  122. }
  123. int counter = 0;
  124. for (int i = 0; i < N; i++) {
  125. for (int j = 0; j < M; j++) {
  126. if (matrix[i][j] == -1)
  127. counter++;
  128. }
  129. }
  130.  
  131. cout<<counter;
  132.  
  133. for (int i = 0; i < N; ++i)
  134. delete [] matrix[i];
  135. delete [] matrix;
  136.  
  137. return 0;
  138. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement