Question

C Programming Language

Problem Title: Komodo National Park

Do You know that Komodo National Park, located in Nusa Tenggara Timur (NTT), is a
World Heritage Site by UNESCO, the specialized agency under United Nations (UN).

One day, Lili and Bibi were on vacation on one of the islands in the Komodo National

Park area and they just realized that they were living alone on that island because the cot-
tage owner was completing his unfinished business on the main island. We all know that

Komodo, as the endemic island, live in this archipelago. Lili is very worried, and won-
dering is there a barrier between the komodos on the island and their cottage. Lili once

read an article that said that when there is no food supply, komodos can prey on humans.

You, as the person who took Lili and Bibi to the island, are trying to whether the con-
ditions are safe for them to live on the island or not.

The map contains several characters that described the island with the cottage. You may
assume that the island can fit in the map and the map always in rectangular form. The
characters inside the map are described below.
• S - indicates sea that surround the island. You may assume that all area outside
the map is always ocean area.
• H - is the location of the cottage that Lili and Bibi want to stay. It is guaranteed
that there is only one cottage in the island.
• K - indicates the position of all komodos in the island. Komodo is able to move
north, west, south, and east. Komodos in the island also quite lazy to swim or even
touch the water.

• F - is the secure barrier between the komodos and the island’s visitor.
• L - is the empty area inside the island.

Help Lili and Bibi to make sure their own security and safety from the dangerous Komodo.
You need to count how many dangerous Komodo as their threats. If it is not safe for
them, they should leave the island as soon as possible.

Format Input

Input consists of one integer T - number of test case. For every test case, two integers
follow - N and M - number of rows and columns on the map. Then, N lines follow.
Those N lines contain M characters for each line. All characters have been explained
above.

Format Output

Output should be expressed in format ”Case #X: Y ” - X is the number of test case, and
followed by Y - number of Komodo that should be secured from them.

Constraints

• 1 ≤ T ≤ 1000
• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 100

Sample Input & Output (standard input & output)

2

3 3

SSS

SHS

KSS

Case #1: 0

4 5

SKKKS

SKKKS

SSHSS

SSSSS

Case #2: 6

Answer 1

logic:

use dfs to traverse the map starting with the positio nof H whenever encounter K increment ans and in case of S and F return from the current recursion.

code screenshot:

sample output:

code:

#include<stdio.h>
// function that calculate number of danger Komodo
void countdanger(int ix,int iy,int vis[101][101],char mat[101][101],int n,int m,int *ans){

   // if the current index is out of range return
   if(ix<0||ix>=n||iy<0||iy>=m){
       return;
   }

     // if the current index has been already visited return
   if(vis[ix][iy]){
       return;
   }

   // visit the current index
   vis[ix][iy]=1;
   // if the current index is sea or F it is safe so return
  
   if(mat[ix][iy]=='S'||mat[ix][iy]=='F'){
       return;
   }

   // if the current is K increment ans
   if(mat[ix][iy] =='K'){
       (*ans)++;
   }

   // recursive call to check in south ix+1, iy
   countdanger(ix+1,iy,vis,mat,n,m,ans);
   // recursive call to check in east ix, iy+1
   countdanger(ix,iy+1,vis,mat,n,m,ans);
   // recursive call to check in north ix11, iy
   countdanger(ix-1,iy,vis,mat,n,m,ans);
   // recursive call to check in west ix, iy-1
   countdanger(ix,iy-1,vis,mat,n,m,ans);
  

}
int main(){
   int t;
   scanf("%d",&t);
   int n,m;
   int stx,sty;      // variable to store staring x and y
   int caseno=1;     // variable to keep track of case
   char mat[101][101];
   int vis[101][101];   // 2d matrix to keep track of visited position

   while(t--){
      
          // initialising visited of all position to false
       for(int i=0;i<n;i++){
           for(int j=0;j<m;j++){

               vis[i][j]=0;

           }
       }  
      
       scanf("%d%d",&n,&m);                      // reading n m
      

       for(int i=0;i<n;i++){                      // READING N STRING
           scanf("%s",mat[i]);
       }

       for(int i=0;i<n;i++){           
           for(int j=0;j<m;j++){

              
               if( mat[i][j] == 'H'){           // checking for H to get starting position
                   stx=i;
                   sty=j;
               }

           }
       }

       int ans=0;

       countdanger(stx,sty,vis,mat,n,m,&ans);      // calling dfs from the starting position
      
       printf("Case #%d: %d\n",caseno,ans);

       caseno++;
   }
}