Raj and New Ball

help
, , ,
1

Raj wants Ball. Basically he is standing left top corner of a N X M grid and ball is at the bottom right corner of the grid. Each cell of the grid is either ‘0’ or ‘1’. He can only move to right and down from a cell.
But he can’t just reach the bottom right corner. In order to get ball, he needs to choose a path such that in the path the length of consecutive ‘0’ he encounters should be maximum.

You are given a grid G, print the number of consecutive ‘0’ in the path he chooses.

INPUT

First line contains
N and M Next N line contains M integers of G
OUTPUT

Print the number of consecutive ‘0’ in the path he chooses

CONSTRAINTS
N <1000 && M<1000

Sample Output
3 3
1 0 1
1 0 0
1 1 1
ans is 3 as path Raj will choose will be:

(0,0)->(0,1)->(1,1)->(1,2)->(2,2).
In this path the maximum number of consecutive ‘0’ are at (0,1),(1,1) and (1,2) which is total 3.

2

Hi, I am Raj and I think, I can answer this question :slight_smile:

int dp[1001][1001][2];
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n, vector<int>(m));
    
    rep(i, 0, n) {
        rep(j, 0, m) cin >> v[i][j];
    }
    if (!v[0][0]) dp[0][0][1] = 1;
    rep(j, 1, m) {
        if (v[0][j]) {
            dp[0][j][0] = dp[0][j - 1][0];
            dp[0][j][1] = 0;
        }
        else {
            dp[0][j][0] = max(dp[0][j - 1][0], 1 + dp[0][j - 1][1]);
            dp[0][j][1] = dp[0][j - 1][1] + 1;
        }
    }   
    
    rep(i, 1, n) {
        if (v[i][0]) {
            dp[i][0][0] = dp[i - 1][0][0];
            dp[i][0][1] = 0;
        }
        else {
            dp[i][0][0] = max(dp[i - 1][0][0], 1 + dp[i - 1][0][1]);
            dp[i][0][1] = dp[i - 1][0][1] + 1;
        }
    }
    rep(i, 1, n) {
        rep(j, 1, m) {
            if (v[i][j]) {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]);
                dp[i][j][1] = 0;
            }
            else {
                dp[i][j][0] = max(dp[i - 1][j][0], 1 + dp[i - 1][j][1]);
                dp[i][j][0] = max(dp[i][j][0], max(dp[i][j - 1][0], 1 + dp[i][j - 1][1]));
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]) + 1;
            }
        } 
    }
    cout << dp[n - 1][m - 1][0];
}

I can tell you the logic but i haven’t check my code for other test cases.

Logic
dp[i][j][0] stores the maximum number of consecutive 0s from any path (0, 0) to (i, j)
And
dp[i][j][1] stores the currently number of consecutive 0s, which can become maximum number no. of zeros in future.

Example
n = 1, m = 9
Index -> 1 2 3 4 5 6 7 8 9
value -> 1 0 0 1 0 0 0 1 0

You can easily see dp[0][6][0] = 2 but dp[0][7][0] = 3
so transition is happening like this dp[0][7][0] = max(dp[0][6][0], dp[0][6][1] + 1), where dp[0][6][1] = 2 (Currently consecutive zeros till 6).

Similarly for the index 9 dp[0][9][0] = 3 and dp[0][9][1] = 1

Hope you can understand my code further.

3

I got your logic , very well explained.
But I tried its dp solution without third field and was maintaining a variable for dp[I][j][1]
, but it didn’t worked . Thanks anyways …V