Smilodon is a ferocious animal which used to live during the Pleistocene epoch (2.5 mya–10,000 years ago). Scientists successfully created few smilodons in an experimental DNA research. A park is established and those smilodons are kept in a cage for visitors. This park consists of Grasslands(G), Mountains(M) and Waterbodies(W) and it has three gates (situated in grasslands only). Below is a sample layout.
Before opening the park, club authority decides to calculate Safety index of the park. The procedure of the calculation is described below. Please help them to calculate. Safety Index calculation:
Assume a person stands on grassland(x) and a Smilodon escapes from the cage situated on grassland(y). If the person can escape from any of those three gates before the Smilodon able to catch him, then the grassland(x) is called safe else it is unsafe. A person and a Smilodon both take 1 second to move from one area to another adjacent area(top, bottom, left or right) but a person can move only over grasslands though Smilodon can move over grasslands and mountains. If any grassland is unreachable for Smilodon(maybe it is unreachable for any person also), to increase safe index value Club Authority use to mark those grasslands as safe land. Explained below
For the above layout, there is only one gate at (4,6) Y is the position of Smilodon’s cage
X is not safe area Z is a safe area as is it not possible for smilodon to reach z
Safety index=(total grassland areas which are safe*100)/total grassland area.
Constraints:
3<= R,C <= 10^3
Gates are situated on grasslands only and at the edge of the park. The cage is also situated in grassland only. The position of the cage and the position of three gates are different.
Input Format:
The first line of the input contains two space-separated integers R and C, denoting the size of the park (R*C) The second line contains eight space-separated integers where First two integers represent the position of the first gate 3rd and 4th integers represent the position of second gate 5th and 6th integers represent the position of third gate respectively The last two integers represent the position of the cage Next R lines, each contains space separated C number of characters. These R lines represent the park layout.
Output:
Safety Index accurate up to two decimal places using Half-up Rounding method.
Example 1
Input:
4 4
1 1 2 1 3 1 1 3
G G G G
G W W M
G G W W
M G M M
Output
75.00
Explanation:
Safety Index= (6*100)/8
Example 2
Input:
4 6
1 6 3 6 4 6 3 4
W M G G G G
M G W G M M
G W G G G G
W G W M W G
Output:
69.23
Solution: In C
#include<stdio.h>
int A[50][50]={0};
int vis[50][50];
int path(int i,int j,int n,int dn,int dm){
vis[i][j]=1;
if(i<0||j<0||i>=n||j>=n) return 0;
if(i==dn&&j==dm) return 1;
int sum=0;
for(int ii=0;ii<5;ii++){
if(!vis[i][j-1]&&A[i][j]) sum|=path(i,j-1,n,dn,dm);
if(!vis[i+1][j]&&A[i][j]) sum|=path(i+1,j,n,dn,dm);
if(!vis[i-1][j]&&A[i][j]) sum|=path(i-1,j,n,dn,dm);
if(!vis[i][j+1]&&A[i][j]) sum|=path(i,j+1,n,dn,dm);
}
vis[i][j]=0;
return sum;
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
int x1,y1,x2,y2,x3,y3,x4,y4;
scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
int count=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
char c;
scanf("%c",&c);
if(c=='G') A[i][j]=1,count++;
}
}
x4--;y4--;
A[x4][y4]=0;
int g=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(A[i][j]){
if(path(i,j,n,x4,y4)) A[i][j]=0;
if(A[i][j]) g++;
}
}
}
printf("%f",(float)(100*(g/10?g-2:g))/(float)count);
}Solution: In Java
package demo;
import java.util.Scanner;
class DemoTranslation {
public static int[][] a = new int[50][50];
public static int[][] vis = new int[50][50];
public static int path(int i, int j, int n, int dn, int dm) {
vis[i][j] = 1;
if(i < 0 || j < 0 || i >= n || j >= n) {
return 0;
}
if(i == dn && j == dm) {
return 1;
}
int sum = 0;
for(int ii = 0; ii < 5; ii++) {
if(vis[i][j - 1] == 0 && a[i][j] != 0) {
sum |= path(i, j - 1, n, dn, dm);
}
if(vis[i + 1][j] == 0 && a[i][j] != 0) {
sum |= path(i + 1, j, n, dn, dm);
}
if(vis[i - 1][j] == 0 && a[i][j] != 0) {
sum |= path(i - 1, j, n, dn, dm);
}
if(vis[i][j + 1] == 0 && a[i][j] != 0) {
sum |= path(i, j + 1, n, dn, dm);
}
}
vis[i][j] = 0;
return sum;
}
public static void main(String[] args) {
int n, m;
n = STDIN_SCANNER.nextInt();
m = STDIN_SCANNER.nextInt();
int x1, y1, x2, y2, x3, y3, x4, y4;
x1 = STDIN_SCANNER.nextInt();
y1 = STDIN_SCANNER.nextInt();
x2 = STDIN_SCANNER.nextInt();
y2 = STDIN_SCANNER.nextInt();
x3 = STDIN_SCANNER.nextInt();
y3 = STDIN_SCANNER.nextInt();
x4 = STDIN_SCANNER.nextInt();
y4 = STDIN_SCANNER.nextInt();
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
byte c;
c = (byte)nextChar(STDIN_SCANNER);
if(c == 'G') {
a[i][j] = 1;
count++;
}
}
}
x4--;
y4--;
a[x4][y4] = 0;
int g = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(a[i][j] != 0) {
if(path(i, j, n, x4, y4) != 0) {
a[i][j] = 0;
}
if(a[i][j] != 0) {
g++;
}
}
}
}
System.out.printf("%f", (float)(100 * (g / 10 != 0 ? g - 2 : g)) / (float)count);
}
public final static Scanner STDIN_SCANNER = new Scanner(System.in);
/**
* This method is missing from the Scanner interface.
*/
public final static int nextChar(Scanner scanner) {
scanner.useDelimiter("");
int ret = scanner.next().charAt(0);
scanner.reset();
return ret;
}
}Also Checkout