Header Ads Widget

Devu and Perfume | codechef solution

Rajnish Tripathi 05:30

There is a haunted town called HauntedLand. The structure of HauntedLand can be thought of as a grid of size n * m. There is a house in each cell of the grid. Some people have fled from their houses because they were haunted. '.' represents a haunted house whereas '*' represents a house in which people are living.

One day, Devu, the famous perfumer came to town with a perfume whose smell can hypnotize people. Devu can put the perfume in at most one of the houses. This takes Devu one second. Then, the perfume spreads from one house (need not be inhabited by people) to all its adjacent houses in one second, and the cycle continues. Two houses are said to be a adjacent to each other, if they share a corner or an edge, i.e., each house (except those on the boundaries) will have 8 adjacent houses.

You want to save people from Devu's dark perfumery by sending them a message to flee from the town. So, you need to estimate the minimum amount of time Devu needs to hypnotize all the people? Note that if there are no houses inhabited by people, Devu doesn't need to put perfume in any cell.

Input

The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.

First line of each test case contains two space separated integers n, m denoting the dimensions of the town.

For each of next n lines, each line has m characters (without any space) denoting a row of houses of the town.

Output

For each test case, output a single integer corresponding to the answer of the problem.

Constraints

  • 1 ≤ T ≤ 20

Subtask #1: (40 points)

  • 1 ≤ n, m ≤ 100
Subtask #2: (60 points)
  • 1 ≤ n, m ≤ 1000

Sample 1:

Input
Output
2
2 2
*.
..
3 4
.*..
***.
.*..
1
2

Explanation:

In the first example, it will take Devu one second for putting the perfume at the only house. So, the answer is 1.

In the second example, He will first put the perfume at the * at cell (1, 1) (assuming 0-based indexing). Now, it will take Devu 1 secs to put perfume. In the next second, the perfume will spread to all of its adjacent cells, thus making each house haunted. So, the answer is 2. 


Code(C++):-

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000007
#define ll long long
#define endl "\n"


void solve(){
    ll n,m;cin>>n>>m;
    char a[n][m];
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {

            char temp;cin>>temp;
            a[i][j]=temp;       }
    }
    int maxrow=-1,maxcol=-1,minrow=MAX,mincol=MAX;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if(a[i][j]=='*'){
                if(minrow>i){minrow=i;}
                if(maxrow<i) maxrow=i;
                if(mincol>j){mincol=j;}
                if(maxcol<j) maxcol=j;
            }
        }
    }
    if(maxrow==-1){cout<<0<<endl;return;}
    
        int t1,t2;
    if((maxrow-minrow)&1){t1=(maxrow-minrow)/2+1;}
    else t1=(maxrow-minrow)/2;
    if((maxcol-mincol)&1){t2=(maxcol-mincol)/2+1;}
    else t2=(maxcol-mincol)/2;
    cout<<max(t1,t2)+1<<endl;
    

}

int main(){

    int t;cin>>t;

    while(t--){
        solve();
    }
    
    
    
return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int t=Integer.parseInt(br.readLine()),n,m,x,y,x1,y1,d;
        while(t-->0)
        {
         String s[]=br.readLine().split(" ");
         n=Integer.parseInt(s[0]);m=Integer.parseInt(s[1]);
         x=0;y=0;x1=n;y1=m;d=0;
         for(int i=0;i<n;i++)
         {
         String su=br.readLine();
     for(int j=0;j<m;j++)
     if(su.charAt(j)=='*')
     {
     d=1;
     if(j>y)
     y=j;
     if(j<y1)
     y1=j;
     if(i>x)
     x=i;
     if(i<x1)
     x1=i;
     }
         }
         if(d==0)
         System.out.println(0);
         else
         System.out.println(((int)Math.max(x-x1,y-y1)+1)/2+1);
         }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments