Your local supermarket is giving away a shopping trolley full of Ramadan groceries for a smart...

  

Transcribed Image Text:

Your local supermarket is giving away a shopping trolley full of Ramadan groceries for a smart shopper. A lucky draw is organized daily among all shoppers to select three shoppers. The shoppers drawn walk through a giant-sized (N×N) board with values at each of the squares on the board. The shoppers must start at square S and finish at square F of the board, by taking steps either to the right, left, down or up (moving diagonally is not allowed) incurring the minimum total. The supermarket manager needs to know the minimum total to go from start to destination to decide the winner of the trolly. S F 1.2 Tasks You are required to: 1. Write an algorithm to find the minimum total to go from start to finish. Your algorithm should a. Get the size of the board, NxN. b. Read N lines, each of which consisting of N integer values, separated by a single space, representing the value V on each square of the board. c. Calculate the minimum total to go from start to destination and display on the screen. 2. Calculate the time and space complexities of your algorithm. 3. Implement your algorithm using Java code. 1.3 Sample Run Enter the dimensions of the board: 3 3 Enter the values of the secures: 84 71 90 68 35 98 41 89 19 The minimum total cost is 295 Explanation The path that yields the minimum total (295) is highlighted. 84 71 90 68 35 98 41 89 19 Your local supermarket is giving away a shopping trolley full of Ramadan groceries for a smart shopper. A lucky draw is organized daily among all shoppers to select three shoppers. The shoppers drawn walk through a giant-sized (N×N) board with values at each of the squares on the board. The shoppers must start at square S and finish at square F of the board, by taking steps either to the right, left, down or up (moving diagonally is not allowed) incurring the minimum total. The supermarket manager needs to know the minimum total to go from start to destination to decide the winner of the trolly. S F 1.2 Tasks You are required to: 1. Write an algorithm to find the minimum total to go from start to finish. Your algorithm should a. Get the size of the board, NxN. b. Read N lines, each of which consisting of N integer values, separated by a single space, representing the value V on each square of the board. c. Calculate the minimum total to go from start to destination and display on the screen. 2. Calculate the time and space complexities of your algorithm. 3. Implement your algorithm using Java code. 1.3 Sample Run Enter the dimensions of the board: 3 3 Enter the values of the secures: 84 71 90 68 35 98 41 89 19 The minimum total cost is 295 Explanation The path that yields the minimum total (295) is highlighted. 84 71 90 68 35 98 41 89 19