You are given an N x N grid 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 0 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.
Answers
Answer:
.
Explanation:
Answer:
#include<stdio.h>
int main()
{
int n,i,j,sum=0;
scanf("%d",&n);
int a[n][n],b[n][n];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
b[0][0]=0;
if(i==0&&j!=0)
{
sum=(b[i][j]/2)+a[i][j];
b[i][j]=sum;
}
if(j==0&&i!=0)
{
sum=(b[i][j]/2)+a[i][j];
b[i][j]=sum;
}
if(i!=0&&j!=0)
{
if(b[i-1][j]>b[i][j-1])
{
sum=(b[i][j-1]/2)+a[i][j];
b[i][j]=sum;
}
else
{
sum=(b[i-1][j]/2)+a[i][j];
b[i][j]=sum;
}
}
}
}
printf("%d",b[n-1][n-1]);
return 0;
}
Explanation: