Question

quiz 1 write your java code Have the function SearchingChallenge(strArr) read the array of strings stored in strArr which will be a 4x4 matrix of the characters 'C', 'H', 'F', 'O', where C represents Charlie the dog, H represents its home, F represents dog food, and O represents and empty space in the grid. Your goal is to figure out the least amount of moves required to get Charlie to grab each piece of food in the grid by moving up, down, left, or right, and then make it home right after. Charlie cannot move onto the home before all pieces of food have been collected. For example: if strArr is ["FOOF", "OCOO", "OOOH", "FOOO"], then this looks like the following grid: For the input above, the least amount of steps where the dog can reach each piece of food, and then return home is 11 steps, so your program should return the number 11. The grid will always contain between 1 and 8 pieces of food. Examples Input: {"OOOO", "OOFF", "OCHO", "OFOO"} Output: 7 Input: {"FOOO", "OCOH", "OFOF", "OFOO"} Output: 10 ---------------------------------- you have the following code what edit on it import java.util.*; import java.io.*; class Main { public static String SearchingChallenge(String[] strArr) { // code goes here return strArr[0]; } public static void main (String[] args) { // keep this function call here Scanner s = new Scanner(System.in); System.out.print(SearchingChallenge(s.nextLine())); } }

Answer 1

Java code for above problem

import java.util.*;
import java.io.*;
class Main
{
   static int min_distance=0;
   static int x[]={-1,0,1,0};
   static int y[]={0,1,0,-1};
   public static String SearchingChallenge(String strArr)
   {
       min_distance=Integer.MAX_VALUE;
       String [] arr=strArr.split(" ");
       Point start=null,end=null;
       int food_count=0;
       int R=arr.length;
       int C=arr[0].length();
       boolean [][] visited=new boolean[R][C];
       for(int i=0;i<R;i++)
       {
           for(int j=0;j<C;j++)
           {
               if(arr[i].charAt(j)=='C')
                   start=new Point(i,j);
               else if(arr[i].charAt(j)=='H')
                   end=new Point(i,j);
               else if(arr[i].charAt(j)=='F')
                   food_count++;
           }
       }
       if(start==null || end==null)
           return String.valueOf(min_distance);
       min_path(arr,R,C,visited,start,end,food_count,0);
       return String.valueOf(min_distance);
   }
   public static void min_path(String arr[],int R,int C,boolean visited[][],Point start,Point end,int food_count,int path_count)
   {
       if(visited[start.i][start.j])
           return;
       if(start.i==end.i && start.j==end.j && food_count==0)
       {
           min_distance=Math.min(min_distance,path_count);
           return;
       }
       visited[start.i][start.j]=true;
       for(int a=0;a<4;a++)
       {
           int newX=start.i+x[a];
           int newY=start.j+y[a];
           if(newX>=0 && newX<R && newY>=0 && newY<C && !visited[newX][newY])
           {
               if(arr[newX].charAt(newY)=='F')
                   min_path(arr,R,C,visited,new Point(newX,newY),end,food_count-1,path_count+1);
               else
                   min_path(arr,R,C,visited,new Point(newX,newY),end,food_count,path_count+1);
           }
       }
       visited[start.i][start.j]=false;
   }
   public static void main (String[] args)
   {
       Scanner s = new Scanner(System.in);
       System.out.println(SearchingChallenge(s.nextLine()));
   }
}
class Point
{
   int i,j;
   Point(int i,int j)
   {
       this.i=i;
       this.j=j;
   }
   public String toString()
   {
       return i+" "+j;
   }
}

Sample output

(a):

if input is "OOOO OOFF OCHO OFOO", then output is 7.

(b):

if input is "FOOO OCOH OFOF OFOO", then output is 10.

Mention in comments if any mistakes or errors are found. Thank you.