Vpropel VIT | POD | 09/05/2020 | Help the doctor | 17

help_the_doctor.cpp

#include<iostream>
#include<vector>
/*
void display(std::vector<std::vector<int>> &grid,int r,int c)
{
    for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                std::cout<<grid[i][j]<<'\t';
            }
            std::cout<<'\n';
        }
        std::cout<<'\n';
}
*/
int check(std::vector<std::vector<int>> &grid,int r,int c)
{
    bool chk=false;
    int days=0;
    int no1=0;
    while(1)
    {   
        std::vector<std::vector<int>>temp;
        temp=grid;
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(grid[i][j]==1)
                    no1++;
                if(grid[i][j]==2 && i-1>=0)
                {
                    if(grid[i-1][j]==1)
                    {
                        chk=true;
                        temp[i-1][j]=2;
                    }
                }
                if(grid[i][j]==2 && i+1<r)
                {
                    if(grid[i+1][j]==1)
                    {
                        chk=true;
                        temp[i+1][j]=2;
                    }
                }
                if(grid[i][j]==2 && j-1>=0)
                {
                    if(grid[i][j-1]==1)
                    {
                        chk=true;
                        temp[i][j-1]=2;
                    }
                }
                if(grid[i][j]==2 && j+1<c)
                {
                    if(grid[i][j+1]==1)
                    {
                        chk=true;
                        temp[i][j+1]=2;
                    }
                }
            }
        }
        grid=temp;
        //display(grid,r,c);
        if(chk==true)
        {
            days++;
            chk=false;
        }
        else if(chk==false && no1!=0)
            return -1;
        else
            return days;
        no1=0;
    }
}
int main()
{
    int r,c;
    std::cin>>r>>c;
    std::vector<std::vector<int>>grid;
    for(int i=0;i<r;i++)
    {
        std::vector<int> temp;
        for(int j=0;j<c;j++)
        {
            int t;
            std::cin>>t;
            temp.push_back(t);
        }
        grid.push_back(temp);
    }
    std::cout<<check(grid,r,c);
    return 0;
}

//Aliter
/*
 #include<iostream>
#include<vector>
using namespace std;

int main() {
	int r, c;
	cin >> r >> c;
	vector<vector<int>> v;
	for (int i = 0; i < r; i++) {
		vector<int> temp;
		for (int j = 0; j < c; j++) {
			int x;
			cin >> x;
			temp.push_back(x);
		}
		v.push_back(temp);
	}
	// 2 1 1
	// 3 1 1
	// 1 3 1
	int days = 0;
	int no1 = 0;
	while (1) {
		int no1_temp = 0;
		vector<vector<int>> vtemp = v;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (v[i][j] == 1)
					no1_temp++;
				else if (v[i][j] == 2)
				{
					if (j + 1 < c && v[i][j+1]!=3)
						vtemp[i][j + 1] = 2;
					if (i + 1 < r && v[i+1][j] != 3)
						vtemp[i + 1][j] = 2;
					if (j - 1 >= 0 && v[i][j - 1] != 3)
						vtemp[i][j - 1] = 2;
					if (i - 1 >= 0 && v[i - 1][j] != 3)
						vtemp[i - 1][j] = 2;
				}
			}
		}
		if (no1_temp == 0) {
			cout << days;
			return 0;
		}
		if (no1 == no1_temp) {
			cout << -1;
			return 0;
		}
		no1 = no1_temp;
		v = vtemp;
		days++;
	}

}

*/

Question(help_the_doctor).txt

Help the doctor
Sabarish, A doctor forms a grid where each cell represents the condition of a patient. 

The cell can take any of the three values as follows:

              1-The person is virus free

              2-The person is infected with the virus

               3-Empty cell

It takes one day for the virus to spread from one person to another. 

Every day any virus free person who is adjacent (4-directionally) to the infected person catches the disease.

Given the initial grid help the doctor to find the minimum number of days that must elapse until 

everyone has been infected. If this impossible return -1.

Example:-

Suppose the input grid is 2 1 1 

                                            1 1 3

                                            3 1 1

After day 1 the grid will be    2 2 1

                                                  2 1 3

                                                  3 1 1

After day 2 the grid  will be  2 2 2

                                                 2 2 3

                                                 3 1 1

 

After day 3 the grid will be 2 2 2

                                               2 2 3

                                               3 2 1

After day 4 the grid will be 2 2 2

                                               2 2 3

                                               3 2 2

So, the minimum number of days is 4

Input format:-

Numbers of row in the grid

Numbers of column in the grid

Contents of the grid(next row*column lines)

Output format:-

Minimum number of days required