Samsung Interview Question
Software EngineersCountry: India
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
/**
*
* @author SVN SAIRAM
*/
public class JavaApplication96 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[][]=new int[n][5];
for(int i=0;i<n;i++)
{
for(int j=0;j<5;j++)
{
arr[i][j]=sc.nextInt();
}
}
System.out.println(repeat(n,arr,1,2,n,0));
}
public static int repeat(int pos,int [][]arr,int bomb,int place,int n,int coins)
{ //System.out.println(pos+" "+place+" "+bomb+" "+coins);
if(pos<0||place>=5||place<0)
return coins;
if(pos!=n){
if(arr[pos][place]==2)
{
return coins;
}
if(arr[pos][place]==1)
coins++;
}
int brr[][]=new int[n][n];
if(bomb==1)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<5;j++)
{
brr[i][j]=arr[i][j];
}
}
int count=5;
int index=pos;
while(index-->0&&count-->0)
{
for(int j=0;j<5;j++)
{
if(brr[index][j]==2)
{
brr[index][j]=0;
}
}
}
}
if(bomb==1)
{
int position=pos-1;
int nm=place;
int lm=place-1;
int rm=place+1;
int x=repeat(position,arr,1,lm, n,coins);
int y=repeat(position,arr,1,nm, n,coins);
int z=repeat(position,arr,1,rm,n,coins);
int a=repeat(position,brr,0,lm,n,coins);
int b=repeat(position,brr,0,nm,n,coins);
int c=repeat(position,brr,0,rm,n,coins);
int d=Math.max(Math.max(Math.max(x, y), Math.max(z, a)),Math.max(b, c));
return d;
}
else
{int position=pos-1;
int nm=place;
int lm=place-1;
int rm=place+1;
int z=Math.max(repeat(position,arr,0,lm,n,coins), repeat(position,arr,0,nm,n,coins));
return Math.max(z, repeat(position,arr,0,rm,n,coins));
}
}
}
this is 3d dp solution.
#include<iostream>
using namespace std;
int rec(int arr[][5],int dp[][2][5],int curr_i,int curr_j,int bomb,int x)
{
if(dp[curr_i][bomb][curr_j]!=-1){
// cout<<"OVERLAP!"<<endl;
return dp[curr_i][bomb][curr_j];
}
if(bomb==0) //no bomb left
{
if(curr_i<x)
{
if(curr_i-1>=0)
{
int maxcoin=-1;
if(curr_j-1>=0)
{
if(arr[curr_i-1][curr_j-1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x)+1);
}
else if(arr[curr_i-1][curr_j-1]==0)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x));
}
}
if(arr[curr_i-1][curr_j]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x)+1);
}
else if(arr[curr_i-1][curr_j]==0)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x));
}
if(curr_j+1<5)
{
if(arr[curr_i-1][curr_j+1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x)+1);
}
else if(arr[curr_i-1][curr_j+1]==0)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x));
}
}
if(maxcoin==-1)
maxcoin=0;
return dp[curr_i][bomb][curr_j]=maxcoin;
}
else
{
return dp[curr_i][bomb][curr_j]=0;
}
}
else
{
int maxcoin=-1;
if(curr_i-1>=0)
{
if(curr_j-1>=0)
{
if(arr[curr_i-1][curr_j-1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x));
}
}
if(arr[curr_i-1][curr_j]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x));
}
if(curr_j+1<5)
{
if(arr[curr_i-1][curr_j+1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x));
}
}
if(maxcoin==-1)
maxcoin=0;
return dp[curr_i][bomb][curr_j]=maxcoin;
}
else
{
return (dp[curr_i][bomb][curr_j]=0);
}
}
}
else
{
if(curr_i-1>=0)
{
int maxcoin=-1;
if(curr_j-1>=0)
{
if(arr[curr_i-1][curr_j-1]==1){
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x)+1);
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,0,curr_i-5)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,0,curr_i-5));
}
}
if(arr[curr_i-1][curr_j]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x)+1);
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,0,curr_i-5)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,0,curr_i-5));
}
if(curr_j+1<5)
{
if(arr[curr_i-1][curr_j+1]==1){
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x)+1);
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,0,curr_i-5)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,0,curr_i-5));
}
}
if(maxcoin==-1)
maxcoin=0;
return dp[curr_i][bomb][curr_j]=maxcoin;
}
else
{
return (dp[curr_i][bomb][curr_j]=0);
}
}
}
int main()
{
int n,m;
cin>>n;
int arr[n][5];
for(int i=0;i<n;i++)
for(int j=0;j<5;j++)
cin>>arr[i][j];
int dp[n+1][2][5];
for(int i=0;i<=n;i++)
for(int j=0;j<2;j++)
for(int k=0;k<5;k++)
dp[i][j][k]=-1;
cout<<rec(arr,dp,n,2,1,-1)<<endl;
return 0;
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
/**
*
* @author SVN SAIRAM
*/
public class JavaApplication96 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[][]=new int[n][5];
for(int i=0;i<n;i++)
{
for(int j=0;j<5;j++)
{
arr[i][j]=sc.nextInt();
}
}
System.out.println(repeat(n,arr,1,2,n,0));
}
public static int repeat(int pos,int [][]arr,int bomb,int place,int n,int coins)
{ //System.out.println(pos+" "+place+" "+bomb+" "+coins);
if(pos<0||place>=5||place<0)
return coins;
if(pos!=n){
if(arr[pos][place]==2)
{
return coins;
}
if(arr[pos][place]==1)
coins++;
}
int brr[][]=new int[n][n];
if(bomb==1)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<5;j++)
{
brr[i][j]=arr[i][j];
}
}
int count=5;
int index=pos;
while(index-->0&&count-->0)
{
for(int j=0;j<5;j++)
{
if(brr[index][j]==2)
{
brr[index][j]=0;
}
}
}
}
if(bomb==1)
{
int position=pos-1;
int nm=place;
int lm=place-1;
int rm=place+1;
int x=repeat(position,arr,1,lm, n,coins);
int y=repeat(position,arr,1,nm, n,coins);
int z=repeat(position,arr,1,rm,n,coins);
int a=repeat(position,brr,0,lm,n,coins);
int b=repeat(position,brr,0,nm,n,coins);
int c=repeat(position,brr,0,rm,n,coins);
int d=Math.max(Math.max(Math.max(x, y), Math.max(z, a)),Math.max(b, c));
return d;
}
else
{int position=pos-1;
int nm=place;
int lm=place-1;
int rm=place+1;
int z=Math.max(repeat(position,arr,0,lm,n,coins), repeat(position,arr,0,nm,n,coins));
return Math.max(z, repeat(position,arr,0,rm,n,coins));
}
}
}
int graph(int n,int x,vector<vector<int > > map , int flag){
int coins=0;
if(x>map[0].size()||x<0)
return -555;
if(n>=map.size())
return -556;
if(map[n][x]==1) coins=1;
if(map[n][x]==2) coins=-1;
int coinsnbomb=max(graph(n+1,x+1,map,flag),max(graph(n+1,x-1,map,flag),graph(n+1,x,map,flag)));
//right
//left
//notmove
int coinsbomb=-555555;
if(flag==1){
vector<pair<int ,int > > temp;
for(int i=n;i<4+n&&i<map.size();i++){
for(int j=0;j<map[0].size();j++){
if(map[i][j]==2){
temp.push_back(make_pair(i,j));
map[i][j]=0;
}
}
}
coinsbomb=max(graph(n+1,x+1,map,0),max(graph(n+1,x,map,0),graph(n+1,x-1,map,0)));
for(int i=0;i<temp.size();i++){
map[temp[i].first][temp[i].second]=2;
}
//bombnotnove
//bombright
// bombleft
}
return max(coinsnbomb,coinsbomb)+coins;
}
#include<iostream>
using namespace std;
int arr[100][5];
int func(int b,int n)
{
int ans=0;
int a[n][5];
for(int i=0;i<n;i++)
{
if(i>=b && i<b+5)
{
for(int j=0;j<5;j++)
{
if(arr[i][j]==2) a[i][j]=0;
else a[i][j]=arr[i][j];
}
}
else for(int j=0;j<5;j++) a[i][j]=arr[i][j];
}
//for(int i=0;i<n;i++) {{for(int j=0;j<5;j++) cout<<a[i][j]<<" ";}cout<<endl;}
int p[5]={-1,-1,0,-1,-1};
int c[5]={-1,-1,-1,-1,-1};
for(int i=n-1;i>=0;i--)
{
//cout<<"level "<<i+1<<" :";
for (int j=0;j<5;j++)
{
if(a[i][j]==2) {c[j]=-1;continue;}
for(int k=max(j-1,0);k<=min(j+1,4);k++)
{
if(p[k]!=-1) c[j]=max(c[j],(p[k]+a[i][j]));
}
ans=max(ans,c[j]);
}
for(int l=0;l<5;l++) p[l]=c[l];
}
return ans;
}
int main()
{
int n,m=5;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){ for(int j=0;j<5;j++) {cin>>arr[i][j];}}
for(int i=0;i<n-4;i++) {ans=max(ans,func(i,n));}
cout<<ans<<endl;
return 0;
}
#include<iostream>
using namespace std;
int arr[100][5];
int func(int b,int n)
{
int ans=0;
int a[n][5];
for(int i=0;i<n;i++)
{
if(i>=b && i<b+5)
{
for(int j=0;j<5;j++)
{
if(arr[i][j]==2) a[i][j]=0;
else a[i][j]=arr[i][j];
}
}
else for(int j=0;j<5;j++) a[i][j]=arr[i][j];
}
//for(int i=0;i<n;i++) {{for(int j=0;j<5;j++) cout<<a[i][j]<<" ";}cout<<endl;}
int p[5]={-1,-1,0,-1,-1};
int c[5]={-1,-1,-1,-1,-1};
for(int i=n-1;i>=0;i--)
{
//cout<<"level "<<i+1<<" :";
for (int j=0;j<5;j++)
{
if(a[i][j]==2) {c[j]=-1;continue;}
for(int k=max(j-1,0);k<=min(j+1,4);k++)
{
if(p[k]!=-1) c[j]=max(c[j],(p[k]+a[i][j]));
}
ans=max(ans,c[j]);
}
for(int l=0;l<5;l++) p[l]=c[l];
}
return ans;
}
int main()
{
int n,m=5;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){ for(int j=0;j<5;j++) {cin>>arr[i][j];}}
for(int i=0;i<n-4;i++) {ans=max(ans,func(i,n));}
cout<<ans<<endl;
return 0;
}
#include<iostream>
using namespace std;
int arr[100][5];
int func(int b,int n)
{
int ans=0;
int a[n][5];
for(int i=0;i<n;i++)
{
if(i>=b && i<b+5)
{
for(int j=0;j<5;j++)
{
if(arr[i][j]==2) a[i][j]=0;
else a[i][j]=arr[i][j];
}
}
else for(int j=0;j<5;j++) a[i][j]=arr[i][j];
}
//for(int i=0;i<n;i++) {{for(int j=0;j<5;j++) cout<<a[i][j]<<" ";}cout<<endl;}
int p[5]={-1,-1,0,-1,-1};
int c[5]={-1,-1,-1,-1,-1};
for(int i=n-1;i>=0;i--)
{
//cout<<"level "<<i+1<<" :";
for (int j=0;j<5;j++)
{
if(a[i][j]==2) {c[j]=-1;continue;}
for(int k=max(j-1,0);k<=min(j+1,4);k++)
{
if(p[k]!=-1) c[j]=max(c[j],(p[k]+a[i][j]));
}
ans=max(ans,c[j]);
}
for(int l=0;l<5;l++) p[l]=c[l];
}
return ans;
}
int main()
{
int n,m=5;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){ for(int j=0;j<5;j++) {cin>>arr[i][j];}}
for(int i=0;i<n-4;i++) {ans=max(ans,func(i,n));}
cout<<ans<<endl;
return 0;
}
#include <iostream>
using namespace std;
int arr[100][5];
int func(int b,int n)
{
int ans=0;
int a[n][5];
for(int i=0;i<n;i++)
{
if(i>=b && i<b+5)
{
for(int j=0;j<5;j++)
{
if(arr[i][j]==2) a[i][j]=0;
else a[i][j]=arr[i][j];
}
}
else for(int j=0;j<5;j++) a[i][j]=arr[i][j];
}
//for(int i=0;i<n;i++) {{for(int j=0;j<5;j++) cout<<a[i][j]<<" ";}cout<<endl;}
int p[5]={-1,-1,0,-1,-1};
int c[5]={-1,-1,-1,-1,-1};
for(int i=n-1;i>=0;i--)
{
//cout<<"level "<<i+1<<" :";
for (int j=0;j<5;j++)
{
if(a[i][j]==2) {c[j]=-1;continue;}
for(int k=max(j-1,0);k<=min(j+1,4);k++)
{
if(p[k]!=-1) c[j]=max(c[j],(p[k]+a[i][j]));
}
ans=max(ans,c[j]);
}
for(int l=0;l<5;l++) p[l]=c[l];
}
return ans;
}
int main()
{
int n,m=5;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){ for(int j=0;j<5;j++) {cin>>arr[i][j];}}
for(int i=0;i<n-4;i++) {ans=max(ans,func(i,n));}
cout<<ans<<endl;
return 0;
}
}}}
#include <iostream>
using namespace std;
int arr[100][5];
int func(int b,int n)
{
int ans=0;
int a[n][5];
for(int i=0;i<n;i++)
{
if(i>=b && i<b+5)
{
for(int j=0;j<5;j++)
{
if(arr[i][j]==2) a[i][j]=0;
else a[i][j]=arr[i][j];
}
}
else for(int j=0;j<5;j++) a[i][j]=arr[i][j];
}
//for(int i=0;i<n;i++) {{for(int j=0;j<5;j++) cout<<a[i][j]<<" ";}cout<<endl;}
int p[5]={-1,-1,0,-1,-1};
int c[5]={-1,-1,-1,-1,-1};
for(int i=n-1;i>=0;i--)
{
//cout<<"level "<<i+1<<" :";
for (int j=0;j<5;j++)
{
if(a[i][j]==2) {c[j]=-1;continue;}
for(int k=max(j-1,0);k<=min(j+1,4);k++)
{
if(p[k]!=-1) c[j]=max(c[j],(p[k]+a[i][j]));
}
ans=max(ans,c[j]);
}
for(int l=0;l<5;l++) p[l]=c[l];
}
return ans;
}
int main()
{
int n,m=5;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){ for(int j=0;j<5;j++) {cin>>arr[i][j];}}
for(int i=0;i<n-4;i++) {ans=max(ans,func(i,n));}
cout<<ans<<endl;
return 0;
}
}}}
#include<iostream>
using namespace std;
int arr[100][5];
int func(int b,int n)
{
int ans=0;
int a[n][5];
for(int i=0;i<n;i++)
{
if(i>=b && i<b+5)
{
for(int j=0;j<5;j++)
{
if(arr[i][j]==2) a[i][j]=0;
else a[i][j]=arr[i][j];
}
}
else for(int j=0;j<5;j++) a[i][j]=arr[i][j];
}
//for(int i=0;i<n;i++) {{for(int j=0;j<5;j++) cout<<a[i][j]<<" ";}cout<<endl;}
int p[5]={-1,-1,0,-1,-1};
int c[5]={-1,-1,-1,-1,-1};
for(int i=n-1;i>=0;i--)
{
//cout<<"level "<<i+1<<" :";
for (int j=0;j<5;j++)
{
if(a[i][j]==2) {c[j]=-1;continue;}
for(int k=max(j-1,0);k<=min(j+1,4);k++)
{
if(p[k]!=-1) c[j]=max(c[j],(p[k]+a[i][j]));
}
ans=max(ans,c[j]);
}
for(int l=0;l<5;l++) p[l]=c[l];
}
return ans;
}
int main()
{
int n,m=5;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){ for(int j=0;j<5;j++) {cin>>arr[i][j];}}
for(int i=0;i<n-4;i++) {ans=max(ans,func(i,n));}
cout<<ans<<endl;
return 0;
}
#include<iostream>
using namespace std;
int arr[100][5];
int func(int b,int n)
{
int ans=0;
int a[n][5];
for(int i=0;i<n;i++)
{
if(i>=b && i<b+5)
{
for(int j=0;j<5;j++)
{
if(arr[i][j]==2) a[i][j]=0;
else a[i][j]=arr[i][j];
}
}
else for(int j=0;j<5;j++) a[i][j]=arr[i][j];
}
//for(int i=0;i<n;i++) {{for(int j=0;j<5;j++) cout<<a[i][j]<<" ";}cout<<endl;}
int p[5]={-1,-1,0,-1,-1};
int c[5]={-1,-1,-1,-1,-1};
for(int i=n-1;i>=0;i--)
{
//cout<<"level "<<i+1<<" :";
for (int j=0;j<5;j++)
{
if(a[i][j]==2) {c[j]=-1;continue;}
for(int k=max(j-1,0);k<=min(j+1,4);k++)
{
if(p[k]!=-1) c[j]=max(c[j],(p[k]+a[i][j]));
}
ans=max(ans,c[j]);
}
for(int l=0;l<5;l++) p[l]=c[l];
}
return ans;
}
int main()
{
int n,m=5;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){ for(int j=0;j<5;j++) {cin>>arr[i][j];}}
for(int i=0;i<n-4;i++) {ans=max(ans,func(i,n));}
cout<<ans<<endl;
return 0;
}
#include<iostream>
using namespace std;
int arr[100][5];
int func(int b,int n)
{
int ans=0;
int a[n][5];
for(int i=0;i<n;i++)
{
if(i>=b && i<b+5)
{
for(int j=0;j<5;j++)
{
if(arr[i][j]==2) a[i][j]=0;
else a[i][j]=arr[i][j];
}
}
else for(int j=0;j<5;j++) a[i][j]=arr[i][j];
}
//for(int i=0;i<n;i++) {{for(int j=0;j<5;j++) cout<<a[i][j]<<" ";}cout<<endl;}
int p[5]={-1,-1,0,-1,-1};
int c[5]={-1,-1,-1,-1,-1};
for(int i=n-1;i>=0;i--)
{
//cout<<"level "<<i+1<<" :";
for (int j=0;j<5;j++)
{
if(a[i][j]==2) {c[j]=-1;continue;}
for(int k=max(j-1,0);k<=min(j+1,4);k++)
{
if(p[k]!=-1) c[j]=max(c[j],(p[k]+a[i][j]));
}
ans=max(ans,c[j]);
}
for(int l=0;l<5;l++) p[l]=c[l];
}
return ans;
}
int main()
{
int n,m=5;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){ for(int j=0;j<5;j++) {cin>>arr[i][j];}}
for(int i=0;i<n-4;i++) {ans=max(ans,func(i,n));}
cout<<ans<<endl;
return 0;
}
import java.util.Scanner;
public class Airplane {
static int max = 0;
public static void main (String args[]) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[][] grid = new int[n+1][5];
boolean bomp = true;
int coins = 0;
for (int i = 0; i < grid.length-1; i++) {
for (int j = 0; j < grid[i].length; j++)
grid[i][j]=s.nextInt();
}
s.close();
// for (int i = 0; i < grid.length; i++) {
// for (int j = 0; j < grid[i].length; j++) {
// System.out.print(grid[i][j]);
// }
// System.out.println();
// }
validate(n+1, 2, bomp, grid, coins);
System.out.println(max);
}
private static void validate(int y, int x, boolean bomp, int[][] grid, int coins) {
// System.out.println( y +" | "+x+" | "+bomp+" | "+coins);
if (y>0 && coins != -1) {
if (x==0) {
move(x+1, y-1,bomp, grid, coins);
move(x,y-1,bomp, grid, coins);
}
if (x==4) {
move(x-1,y-1,bomp, grid, coins);
move(x,y-1,bomp, grid, coins);
}
if (x>0 && x<4) {
move(x+1, y-1,bomp, grid, coins);
move(x,y-1,bomp, grid, coins);
move(x-1,y-1,bomp, grid, coins);
}
}
max(coins);
// System.out.println(coins);
}
private static int max(int coins) {
if (max < coins )
max = coins;
return max;
}
private static void move(int x, int y, boolean bomp, int[][] grid, int coins) {
// System.out.println( y +" | "+x+" | "+bomp+" | "+coins);
if (grid[y][x]==0) {
validate(y, x, bomp, grid, coins);
}
if (grid[y][x]==1) {
validate(y, x, bomp, grid, coins+1);
}
if (grid[y][x]==2) {
if (bomp) {
bomp = false;
for (int i =y ; i>y+5 && i>0 ; i--)
for (int j =0 ; i<5 ; j++)
if (grid[i][j]==2)
grid[i][j]=0;
validate(y, x, bomp, grid, coins);
}else
validate(y, x, bomp, grid, coins-1);
}
}
}
import java.util.Scanner;
public class Airplane {
static int max = 0;
public static void main (String args[]) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[][] grid = new int[n+1][5];
boolean bomp = true;
int coins = 0;
for (int i = 0; i < grid.length-1; i++) {
for (int j = 0; j < grid[i].length; j++)
grid[i][j]=s.nextInt();
}
s.close();
// for (int i = 0; i < grid.length; i++) {
// for (int j = 0; j < grid[i].length; j++) {
// System.out.print(grid[i][j]);
// }
// System.out.println();
// }
validate(n+1, 2, bomp, grid, coins);
System.out.println(max);
}
private static void validate(int y, int x, boolean bomp, int[][] grid, int coins) {
// System.out.println( y +" | "+x+" | "+bomp+" | "+coins);
if (y>0 && coins != -1) {
if (x==0) {
move(x+1, y-1,bomp, grid, coins);
move(x,y-1,bomp, grid, coins);
}
if (x==4) {
move(x-1,y-1,bomp, grid, coins);
move(x,y-1,bomp, grid, coins);
}
if (x>0 && x<4) {
move(x+1, y-1,bomp, grid, coins);
move(x,y-1,bomp, grid, coins);
move(x-1,y-1,bomp, grid, coins);
}
}
max(coins);
// System.out.println(coins);
}
private static int max(int coins) {
if (max < coins )
max = coins;
return max;
}
private static void move(int x, int y, boolean bomp, int[][] grid, int coins) {
// System.out.println( y +" | "+x+" | "+bomp+" | "+coins);
if (grid[y][x]==0) {
validate(y, x, bomp, grid, coins);
}
if (grid[y][x]==1) {
validate(y, x, bomp, grid, coins+1);
}
if (grid[y][x]==2) {
if (bomp) {
bomp = false;
for (int i =y ; i>y+5 && i>0 ; i--)
for (int j =0 ; i<5 ; j++)
if (grid[i][j]==2)
grid[i][j]=0;
validate(y, x, bomp, grid, coins);
}else
validate(y, x, bomp, grid, coins-1);
}
}
}
#include<iostream>
using namespace std;
int rec(int arr[][5],int dp[][2][5],int curr_i,int curr_j,int bomb,int x)
{
if(dp[curr_i][bomb][curr_j]!=-1){
// cout<<"OVERLAP!"<<endl;
return dp[curr_i][bomb][curr_j];
}
if(bomb==0) //no bomb left
{
if(curr_i<x)
{
if(curr_i-1>=0)
{
int maxcoin=-1;
if(curr_j-1>=0)
{
if(arr[curr_i-1][curr_j-1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x)+1);
}
else if(arr[curr_i-1][curr_j-1]==0)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x));
}
}
if(arr[curr_i-1][curr_j]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x)+1);
}
else if(arr[curr_i-1][curr_j]==0)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x));
}
if(curr_j+1<5)
{
if(arr[curr_i-1][curr_j+1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x)+1);
}
else if(arr[curr_i-1][curr_j+1]==0)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x));
}
}
if(maxcoin==-1)
maxcoin=0;
return dp[curr_i][bomb][curr_j]=maxcoin;
}
else
{
return dp[curr_i][bomb][curr_j]=0;
}
}
else
{
int maxcoin=-1;
if(curr_i-1>=0)
{
if(curr_j-1>=0)
{
if(arr[curr_i-1][curr_j-1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x));
}
}
if(arr[curr_i-1][curr_j]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x));
}
if(curr_j+1<5)
{
if(arr[curr_i-1][curr_j+1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x));
}
}
if(maxcoin==-1)
maxcoin=0;
return dp[curr_i][bomb][curr_j]=maxcoin;
}
else
{
return (dp[curr_i][bomb][curr_j]=0);
}
}
}
else
{
if(curr_i-1>=0)
{
int maxcoin=-1;
if(curr_j-1>=0)
{
if(arr[curr_i-1][curr_j-1]==1){
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x)+1);
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,0,curr_i-5)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,0,curr_i-5));
}
}
if(arr[curr_i-1][curr_j]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x)+1);
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,0,curr_i-5)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,0,curr_i-5));
}
if(curr_j+1<5)
{
if(arr[curr_i-1][curr_j+1]==1){
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x)+1);
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,0,curr_i-5)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,0,curr_i-5));
}
}
if(maxcoin==-1)
maxcoin=0;
return dp[curr_i][bomb][curr_j]=maxcoin;
}
else
{
return (dp[curr_i][bomb][curr_j]=0);
}
}
}
int main()
{
int n,m;
cin>>n;
int arr[n][5];
for(int i=0;i<n;i++)
for(int j=0;j<5;j++)
cin>>arr[i][j];
int dp[n+1][2][5];
for(int i=0;i<=n;i++)
for(int j=0;j<2;j++)
for(int k=0;k<5;k++)
dp[i][j][k]=-1;
cout<<rec(arr,dp,n,2,1,-1)<<endl;
return 0;
}
i used 3D dp to solve this problem!
#include<iostream>
using namespace std;
int rec(int arr[][5],int dp[][2][5],int curr_i,int curr_j,int bomb,int x)
{
if(dp[curr_i][bomb][curr_j]!=-1){
// cout<<"OVERLAP!"<<endl;
return dp[curr_i][bomb][curr_j];
}
if(bomb==0) //no bomb left
{
if(curr_i<x)
{
if(curr_i-1>=0)
{
int maxcoin=-1;
if(curr_j-1>=0)
{
if(arr[curr_i-1][curr_j-1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x)+1);
}
else if(arr[curr_i-1][curr_j-1]==0)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x));
}
}
if(arr[curr_i-1][curr_j]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x)+1);
}
else if(arr[curr_i-1][curr_j]==0)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x));
}
if(curr_j+1<5)
{
if(arr[curr_i-1][curr_j+1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x)+1);
}
else if(arr[curr_i-1][curr_j+1]==0)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x));
}
}
if(maxcoin==-1)
maxcoin=0;
return dp[curr_i][bomb][curr_j]=maxcoin;
}
else
{
return dp[curr_i][bomb][curr_j]=0;
}
}
else
{
int maxcoin=-1;
if(curr_i-1>=0)
{
if(curr_j-1>=0)
{
if(arr[curr_i-1][curr_j-1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x));
}
}
if(arr[curr_i-1][curr_j]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x));
}
if(curr_j+1<5)
{
if(arr[curr_i-1][curr_j+1]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x));
}
}
if(maxcoin==-1)
maxcoin=0;
return dp[curr_i][bomb][curr_j]=maxcoin;
}
else
{
return (dp[curr_i][bomb][curr_j]=0);
}
}
}
else
{
if(curr_i-1>=0)
{
int maxcoin=-1;
if(curr_j-1>=0)
{
if(arr[curr_i-1][curr_j-1]==1){
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,bomb,x)+1);
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,0,curr_i-5)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j-1,0,curr_i-5));
}
}
if(arr[curr_i-1][curr_j]==1)
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,bomb,x)+1);
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,0,curr_i-5)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j,0,curr_i-5));
}
if(curr_j+1<5)
{
if(arr[curr_i-1][curr_j+1]==1){
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,bomb,x)+1);
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,0,curr_i-5)+1);
}
else
{
maxcoin=max(maxcoin,rec(arr,dp,curr_i-1,curr_j+1,0,curr_i-5));
}
}
if(maxcoin==-1)
maxcoin=0;
return dp[curr_i][bomb][curr_j]=maxcoin;
}
else
{
return (dp[curr_i][bomb][curr_j]=0);
}
}
}
int main()
{
int n,m;
cin>>n;
int arr[n][5];
for(int i=0;i<n;i++)
for(int j=0;j<5;j++)
cin>>arr[i][j];
int dp[n+1][2][5];
for(int i=0;i<=n;i++)
for(int j=0;j<2;j++)
for(int k=0;k<5;k++)
dp[i][j][k]=-1;
cout<<rec(arr,dp,n,2,1,-1)<<endl;
return 0;
}
Simple Solution using recursion
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package Array_questions;
/**
*
* @author ADMIN
*/
public class Spaceship_bomb {
static int value=0;
public static void main(String[] args)
{
int[][] grid = {{0 ,1 ,0 ,2 ,0},
{0, 2, 2, 2, 1},
{0, 2, 1, 1, 1,},
{1, 0, 1, 0, 0},
{0, 0, 1, 2, 2},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0}};
int[][] grid_dummy = grid;
for(int i=grid.length-1;i>=0;i--)
{
spaceship(grid_dummy,6,2,i,0,0);
grid_dummy = grid;
}
System.out.println(value);
}
public static void spaceship(int[][] grid,int x,int y, int i,int counter,int sum)
{
if(x<0)
{
if(sum > value)
{
value = sum;
}
return;
}
if(grid[x][y] == 2)
{
if(sum > value)
{
value = sum;
}
return;
}
if(i == counter)
{
if(x-5 < 0)
{
for(int l=0;l<=x-1;l++)
{
for(int m=0;m<grid[l].length;m++)
{
if(grid[l][m] == 2)
{
grid[l][m] = 0;
}
}
}
}
else{
for(int l=x-5;l<=x-1;l++)
{
for(int m=0;m<grid[l].length;m++)
{
if(grid[l][m] == 2)
{
grid[l][m] = 0;
}
}
}
}
}
sum = sum + grid[x][y];
if(y-1>=0)
{
spaceship(grid, x-1, y-1, i, ++counter, sum);
}
if(y+1 < grid[x].length)
{
spaceship(grid, x-1, y+1, i, ++counter, sum);
}
spaceship(grid, x-1, y, i, ++counter, sum);
}
}
Simple solution using recursion. Only valid for one test case. You can change it for multiple
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package Array_questions;
/**
*
* @author ADMIN
*/
public class Spaceship_bomb {
static int value=0;
public static void main(String[] args)
{
int[][] grid = {{0 ,1 ,0 ,2 ,0},
{0, 2, 2, 2, 1},
{0, 2, 1, 1, 1,},
{1, 0, 1, 0, 0},
{0, 0, 1, 2, 2},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0}};
int[][] grid_dummy = grid;
for(int i=grid.length-1;i>=0;i--)
{
spaceship(grid_dummy,6,2,i,0,0);
grid_dummy = grid;
}
System.out.println(value);
}
public static void spaceship(int[][] grid,int x,int y, int i,int counter,int sum)
{
if(x<0)
{
if(sum > value)
{
value = sum;
}
return;
}
if(grid[x][y] == 2)
{
if(sum > value)
{
value = sum;
}
return;
}
if(i == counter)
{
if(x-5 < 0)
{
for(int l=0;l<=x-1;l++)
{
for(int m=0;m<grid[l].length;m++)
{
if(grid[l][m] == 2)
{
grid[l][m] = 0;
}
}
}
}
else{
for(int l=x-5;l<=x-1;l++)
{
for(int m=0;m<grid[l].length;m++)
{
if(grid[l][m] == 2)
{
grid[l][m] = 0;
}
}
}
}
}
sum = sum + grid[x][y];
if(y-1>=0)
{
spaceship(grid, x-1, y-1, i, ++counter, sum);
}
if(y+1 < grid[x].length)
{
spaceship(grid, x-1, y+1, i, ++counter, sum);
}
spaceship(grid, x-1, y, i, ++counter, sum);
}
}
package Array_questions;
/**
*
* @author ADMIN
*/
public class Spaceship_bomb {
static int value=0;
public static void main(String[] args)
{
int[][] grid = {{0 ,1 ,0 ,2 ,0},
{0, 2, 2, 2, 1},
{0, 2, 1, 1, 1,},
{1, 0, 1, 0, 0},
{0, 0, 1, 2, 2},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0}};
int[][] grid_dummy = grid;
for(int i=grid.length-1;i>=0;i--)
{
spaceship(grid_dummy,6,2,i,0,0);
grid_dummy = grid;
}
System.out.println(value);
}
public static void spaceship(int[][] grid,int x,int y, int i,int counter,int sum)
{
if(x<0)
{
if(sum > value)
{
value = sum;
}
return;
}
if(grid[x][y] == 2)
{
if(sum > value)
{
value = sum;
}
return;
}
if(i == counter)
{
if(x-5 < 0)
{
for(int l=0;l<=x-1;l++)
{
for(int m=0;m<grid[l].length;m++)
{
if(grid[l][m] == 2)
{
grid[l][m] = 0;
}
}
}
}
else{
for(int l=x-5;l<=x-1;l++)
{
for(int m=0;m<grid[l].length;m++)
{
if(grid[l][m] == 2)
{
grid[l][m] = 0;
}
}
}
}
}
sum = sum + grid[x][y];
if(y-1>=0)
{
spaceship(grid, x-1, y-1, i, ++counter, sum);
}
if(y+1 < grid[x].length)
{
spaceship(grid, x-1, y+1, i, ++counter, sum);
}
spaceship(grid, x-1, y, i, ++counter, sum);
}
}
#include<bits/stdc++.h>
using namespace std;
void destroy( int arr[][5],int i, int n ){
for(int j=1;j<=5&&j<n-i;j++){
for(int k=0;k<5;k++){
if( arr[j+i][k]==2 ){arr[i+j][k]=-1; }
}
}
}
void undestroy( int arr[][5],int i, int n ){
for(int j=1;j<=5&&j<n-i;j++){
for(int k=0;k<5;k++){
if( arr[j+i][k]==-1 ){arr[i+j][k]=2; }
}
}
}
int mxcoins=0;
void bomb (int arr[][5],int flag,int i,int j,int n,int coins)
{
if(j<0||j>=5||i>=n){return ;}
if(i!=-1){
if(arr[i][j]==2){return;}
if(arr[i][j]==1){
coins=coins+arr[i][j];
mxcoins=max(mxcoins,coins);
cout<<i<<" "<<j<<" coins "<<mxcoins<<endl;
}}
bomb(arr,flag,i+1,j-1,n,coins);
bomb(arr,flag,i+1,j,n,coins);
bomb(arr,flag,i+1,j+1,n,coins);
if(!flag ){
destroy(arr,i,n);
bomb(arr,1,i+1,j-1,n,coins);
bomb(arr,1,i+1,j,n,coins);
bomb(arr,1,i+1,j+1,n,coins);
undestroy(arr,i,n);
}
}
int main()
{
int arr[6][5]={{0 ,1 ,0 ,2 ,0},
{0, 2, 2, 2, 1},
{0, 2, 1, 1, 1,},
{1, 0, 1, 0, 0},
{0, 0, 1, 2, 2},
{1, 1, 0, 0, 1}
};
bomb(arr,0,-1,2,6,0);
cout<<mxcoins<<endl;
}
#include<bits/stdc++.h>
using namespace std;
void destroy( int arr[][5],int i, int n ){
for(int j=1;j<=5&&j<n-i;j++){
for(int k=0;k<5;k++){
if( arr[j+i][k]==2 ){arr[i+j][k]=-1; }
}
}
}
void undestroy( int arr[][5],int i, int n ){
for(int j=1;j<=5&&j<n-i;j++){
for(int k=0;k<5;k++){
if( arr[j+i][k]==-1 ){arr[i+j][k]=2; }
}
}
}
int mxcoins=0;
void bomb (int arr[][5],int flag,int i,int j,int n,int coins)
{
if(j<0||j>=5||i>=n){return ;}
if(i!=-1){
if(arr[i][j]==2){return;}
if(arr[i][j]==1){
coins=coins+arr[i][j];
mxcoins=max(mxcoins,coins);
cout<<i<<" "<<j<<" coins "<<mxcoins<<endl;
}}
bomb(arr,flag,i+1,j-1,n,coins);
bomb(arr,flag,i+1,j,n,coins);
bomb(arr,flag,i+1,j+1,n,coins);
if(!flag ){
destroy(arr,i,n);
bomb(arr,1,i+1,j-1,n,coins);
bomb(arr,1,i+1,j,n,coins);
bomb(arr,1,i+1,j+1,n,coins);
undestroy(arr,i,n);
}
}
int main()
{
int arr[6][5]={{0 ,1 ,0 ,2 ,0},
{0, 2, 2, 2, 1},
{0, 2, 1, 1, 1,},
{1, 0, 1, 0, 0},
{0, 0, 1, 2, 2},
{1, 1, 0, 0, 1}
};
bomb(arr,0,-1,2,6,0);
cout<<mxcoins<<endl;
}
#include<bits/stdc++.h>
using namespace std;
void destroy( int arr[][5],int i, int n ){
for(int j=1;j<=5&&j<n-i;j++){
for(int k=0;k<5;k++){
if( arr[j+i][k]==2 ){arr[i+j][k]=-1; }
}
}
}
void undestroy( int arr[][5],int i, int n ){
for(int j=1;j<=5&&j<n-i;j++){
for(int k=0;k<5;k++){
if( arr[j+i][k]==-1 ){arr[i+j][k]=2; }
}
}
}
int mxcoins=0;
void bomb (int arr[][5],int flag,int i,int j,int n,int coins)
{
if(j<0||j>=5||i>=n){return ;}
if(i!=-1){
if(arr[i][j]==2){return;}
if(arr[i][j]==1){
coins=coins+arr[i][j];
mxcoins=max(mxcoins,coins);
cout<<i<<" "<<j<<" coins "<<mxcoins<<endl;
}}
bomb(arr,flag,i+1,j-1,n,coins);
bomb(arr,flag,i+1,j,n,coins);
bomb(arr,flag,i+1,j+1,n,coins);
if(!flag ){
destroy(arr,i,n);
bomb(arr,1,i+1,j-1,n,coins);
bomb(arr,1,i+1,j,n,coins);
bomb(arr,1,i+1,j+1,n,coins);
undestroy(arr,i,n);
}
}
int main()
{
int arr[6][5]={{0 ,1 ,0 ,2 ,0},
{0, 2, 2, 2, 1},
{0, 2, 1, 1, 1,},
{1, 0, 1, 0, 0},
{0, 0, 1, 2, 2},
{1, 1, 0, 0, 1}
};
bomb(arr,0,-1,2,6,0);
cout<<mxcoins<<endl;
}
#include<bits/stdc++.h>
using namespace std;
void destroy( int arr[][5],int i, int n ){
for(int j=1;j<=5&&j<n-i;j++){
for(int k=0;k<5;k++){
if( arr[j+i][k]==2 ){arr[i+j][k]=-1; }
}
}
}
void undestroy( int arr[][5],int i, int n ){
for(int j=1;j<=5&&j<n-i;j++){
for(int k=0;k<5;k++){
if( arr[j+i][k]==-1 ){arr[i+j][k]=2; }
}
}
}
int mxcoins=0;
void bomb (int arr[][5],int flag,int i,int j,int n,int coins)
{
if(j<0||j>=5||i>=n){return ;}
if(i!=-1){
if(arr[i][j]==2){return;}
if(arr[i][j]==1){
coins=coins+arr[i][j];
mxcoins=max(mxcoins,coins);
cout<<i<<" "<<j<<" coins "<<mxcoins<<endl;
}}
bomb(arr,flag,i+1,j-1,n,coins);
bomb(arr,flag,i+1,j,n,coins);
bomb(arr,flag,i+1,j+1,n,coins);
if(!flag ){
destroy(arr,i,n);
bomb(arr,1,i+1,j-1,n,coins);
bomb(arr,1,i+1,j,n,coins);
bomb(arr,1,i+1,j+1,n,coins);
undestroy(arr,i,n);
}
}
int main()
{
int arr[6][5]={{0 ,1 ,0 ,2 ,0},
{0, 2, 2, 2, 1},
{0, 2, 1, 1, 1,},
{1, 0, 1, 0, 0},
{0, 0, 1, 2, 2},
{1, 1, 0, 0, 1}
};
bomb(arr,0,-1,2,6,0);
cout<<mxcoins<<endl;
}
DP
- Anonymous September 11, 2017S can move A, B or C.
X A B C X
X X S X X
If there are 3 candidate of S and each values are 3, 1 and 0.
0 1 1 0 0
0 S S S 0 <-- 0 3 1 0 0
Then we update next upper line with the maximum value between each candidate's moves.
First S = 3
3 4 4 0 0
_ 3 _ _ _
Second S = 1
0 2 2 1 0
_ _ 1 _ _
Third S = 0
0 1 1 0 0
_ _ _ 0 _
The results
3 4 4 1 0
0 3 1 0 0
Sample case
0 1 0 2 0
0 2 2 2 1
0 2 1 1 1
1 0 1 0 0
0 0 1 2 2
1 1 0 0 1
X X S X X <-- 0 0 0 0 0 (Initial)
...
S S X S S <-- 2 3 0 0 5 (Last)
S X X X S <-- 2 0 0 0 5 (5)
S X S S S <-- 2 0 4 4 3 (4)
S S S S X <-- 2 2 3 2 0 (3)
S S S X X <-- 1 1 2 0 0 (2)
X S S S X <-- 0 1 0 0 0 (1)
X X S X X <-- 0 0 0 0 0 (Initial)
In last line, the maximum value is 5.