ONLINE EDITOR (A)
A Board Game
- Problem Description
You are given an NxNgrid of squares. Each square except the top left is filled with a positive integer. You start at the top left corner with a score of O and move to the bottom right square
by moving either right by one square or down by one square. As you move to the new square, your score becomes [S/2] + k, where S was the score at your previous square and k is the
number written in the current square. In the above, (x) is the largest integer which is not greater than x. Thus, (5) is 5, and [5.5) is also 5.
Write a program to find the smallest score with which you can exit the grid.
- Constraints
4<N<= 30
Number in each square <= 1000
Input Format
The first line contains a single integer N representing the size of the grid
The next N lines each having N space separated integers giving the numbers written on successive rows of the grid
Output
The smallest score with which you can exit the grid
Time Limit
Activate Windows
Explanation
Example 1
Answers
Answer:
ok big brother and thanks for suggesting
Answer:
import java.util.Scanner;
public class codevita {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int arr[][]=new int[a][a];
for(int i=0;i<a;i++)
{ for(int j=0;j<a;j++)
{
arr[i][j]=sc.nextInt();
}
}
for(int i=0;i<arr.length;i++)
{ for(int j=0;j<arr[0].length;j++)
{ if(i==0 && j==0)
{
arr[i][j]=0;
}
else if(i==0 && j!=0)
{
arr[i][j]= (int)Math.floor((arr[i][j-1]/2)+arr[i][j]);
}
else if(i!=0 && j==0)
{
arr[i][j]= (int)Math.floor((arr[i-1][j]/2)+arr[i][j]);
}
else
{
int min=Math.min(arr[i][j-1], arr[i-1][j]);
arr[i][j]= (int)Math.floor((min/2)+arr[i][j]);
}
}
}
System.out.println(arr[a-1][a-1]);
}
}
Explanation: Dynamic Problem