Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- struct Node{
- int data;
- Node*next;
- Node(int data){
- this->data=data;
- next=NULL;
- }
- };
- class Queue{
- private:
- Node*head,*tail;
- int size;
- public:
- Queue(){
- head=NULL;
- tail=NULL;
- size=0;
- }
- void enqueue(int value){
- Node*temp=new Node(value);
- if(head==NULL){
- head=temp;
- tail=temp;
- size++;
- return;
- }
- tail->next=temp;
- tail=temp;
- size++;
- }
- void dequeue(){
- if(head==NULL){
- return;
- }
- head=head->next;
- }
- int getX(){
- return head->data;
- }
- int getY(){
- return head->next->data;
- }
- int getSize(){
- return size;
- }
- bool isEmpty() {
- return head == NULL;
- }
- };
- int main() {
- int N, M, T;
- cin >> N >> M >> T;
- if (N<1||M<1||T < 1)
- return 0;
- Queue q;
- Queue helper;
- int xCoord, yCoord;
- int**matrix = new int*[N];
- for (int i = 0; i < N; i++) {
- matrix[i] = new int[M];
- }
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < M; j++) {
- matrix[i][j] = -1;
- }
- }
- while (cin >> xCoord >> yCoord) {
- if (xCoord > N || yCoord > M)
- continue;
- q.enqueue(N - xCoord);
- q.enqueue(yCoord - 1);
- matrix[N - xCoord][yCoord - 1] = 0;
- }
- for (int i = 0; i < T; i++) {
- while (!q.isEmpty()) {
- //At this point we check wether the apples
- //around the current one can be infected
- if (q.getX()+1<N&&matrix[q.getX() + 1][q.getY()] == -1) {
- matrix[q.getX() + 1][q.getY()] = i;
- helper.enqueue(q.getX() + 1);
- helper.enqueue(q.getY());
- }
- if (q.getX()-1>=0&&matrix[q.getX() - 1][q.getY()] == -1) {
- matrix[q.getX() - 1][q.getY()] = i;
- helper.enqueue(q.getX() - 1);
- helper.enqueue(q.getY());
- }
- if (q.getY()+1<M&&matrix[q.getX()][q.getY() + 1] == -1) {
- matrix[q.getX()][q.getY() + 1] = i;
- helper.enqueue(q.getX());
- helper.enqueue(q.getY() + 1);
- }
- if (q.getY()-1>=0&&matrix[q.getX()][q.getY() - 1] == -1) {
- matrix[q.getX()][q.getY() - 1] = i;
- helper.enqueue(q.getX());
- helper.enqueue(q.getY() - 1);
- }
- q.dequeue();
- q.dequeue();
- }
- while (!helper.isEmpty()) {
- //At this point the newly rotten are added
- q.enqueue(helper.getX());
- q.enqueue(helper.getY());
- helper.dequeue();
- helper.dequeue();
- }
- }
- int counter = 0;
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < M; j++) {
- if (matrix[i][j] == -1)
- counter++;
- }
- }
- cout<<counter;
- for (int i = 0; i < N; ++i)
- delete [] matrix[i];
- delete [] matrix;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement