# Count cells in a grid from which maximum number of cells can be reached by K vertical or horizontal jumps

Given a matrix **mat[][]** of dimensions **N*M** and a positive integer **K**, the task is to find the number of cells in a grid from which maximum cells can be reached by **K** jumps in the vertical or horizontal direction.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 3, M = 3, K = 2Output:4Explanation:

The cells represented asXare the cells from which maximum cells (= 2) can be reached by K (= 2) jumps:X O XO O OX O X

Input:N = 5, M = 5, K = 2Output:9

**Approach:** The given problem can be solved by counting the number of possible cells for the rows and columns separately based on the following observations:

- Consider any row, say
**i**such that**i <= K**, then the number of rows from**i**that can be reached using jumps of**K**is**(N – i) / K + 1**. - If the rows say
**i**is**i > K**, then these cells are connected to some row**X**where**X <= K**, hence they are already considered.

Therefore, from the above observations, the idea is to find the count of rows that are connected to the maximum number of rows in a variable, say **count_R**. Similarly, for the columns, find the count of columns that are connected to maximum columns in a variable, say **count_C**.

Now, the number of cells in the grid such that the maximum cell is reachable from that cell with a jump of **K** in the vertical or horizontal direction is given by **(count_R)*(count_C)**.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count the number of cells` `// in the grid such that maximum cell is` `// reachable with a jump of K` `long` `long` `countCells(` `int` `n, ` `int` `m, ` `int` `s)` `{` ` ` `// Maximum reachable rows` ` ` `// from the current row` ` ` `int` `mx1 = -1;` ` ` `// Stores the count of cell that are` ` ` `// reachable from the current row` ` ` `int` `cont1 = 0;` ` ` `for` `(` `int` `i = 0; i < s && i < n; ++i) {` ` ` `// Count of reachable rows` ` ` `int` `aux = (n - (i + 1)) / s + 1;` ` ` `// Update the maximum value` ` ` `if` `(aux > mx1) {` ` ` `mx1 = cont1 = aux;` ` ` `}` ` ` `// Add it to the count` ` ` `else` `if` `(aux == mx1)` ` ` `cont1 += aux;` ` ` `}` ` ` `// Maximum reachable columns from` ` ` `// the current column` ` ` `int` `mx2 = -1;` ` ` `// Stores the count of cell that are` ` ` `// reachable from the current column` ` ` `int` `cont2 = 0;` ` ` `for` `(` `int` `i = 0; i < s && i < m; ++i) {` ` ` `// Count of rechable columns` ` ` `int` `aux = (m - (i + 1)) / s + 1;` ` ` `// Update the maximum value` ` ` `if` `(aux > mx2)` ` ` `mx2 = cont2 = aux;` ` ` `// Add it to the count` ` ` `else` `if` `(aux == mx2)` ` ` `cont2 += aux;` ` ` `}` ` ` `// Return the total count of cells` ` ` `return` `(` `long` `long` `)(cont1 * cont2);` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 5, M = 5, K = 2;` ` ` `cout << countCells(N, M, K);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `class` `GFG` `{` ` ` `// Function to count the number of cells` ` ` `// in the grid such that maximum cell is` ` ` `// reachable with a jump of K` ` ` `public` `static` `long` `countCells(` `int` `n, ` `int` `m, ` `int` `s)` ` ` `{` ` ` ` ` `// Maximum reachable rows` ` ` `// from the current row` ` ` `int` `mx1 = -` `1` `;` ` ` `// Stores the count of cell that are` ` ` `// reachable from the current row` ` ` `int` `cont1 = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < s && i < n; ++i) {` ` ` `// Count of reachable rows` ` ` `int` `aux = (n - (i + ` `1` `)) / s + ` `1` `;` ` ` `// Update the maximum value` ` ` `if` `(aux > mx1) {` ` ` `mx1 = cont1 = aux;` ` ` `}` ` ` `// Add it to the count` ` ` `else` `if` `(aux == mx1)` ` ` `cont1 += aux;` ` ` `}` ` ` `// Maximum reachable columns from` ` ` `// the current column` ` ` `int` `mx2 = -` `1` `;` ` ` `// Stores the count of cell that are` ` ` `// reachable from the current column` ` ` `int` `cont2 = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < s && i < m; ++i) {` ` ` `// Count of rechable columns` ` ` `int` `aux = (m - (i + ` `1` `)) / s + ` `1` `;` ` ` `// Update the maximum value` ` ` `if` `(aux > mx2)` ` ` `mx2 = cont2 = aux;` ` ` `// Add it to the count` ` ` `else` `if` `(aux == mx2)` ` ` `cont2 += aux;` ` ` `}` ` ` `// Return the total count of cells` ` ` `return` `(` `long` `) (cont1 * cont2);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String args[]) {` ` ` `int` `N = ` `5` `, M = ` `5` `, K = ` `2` `;` ` ` `System.out.println(countCells(N, M, K));` ` ` `}` `}` `// This code is contributed by gfgking.` |

## Python3

`# Python 3 program for the above approach` `# Function to count the number of cells` `# in the grid such that maximum cell is` `# reachable with a jump of K` `def` `countCells(n, m, s):` ` ` `# Maximum reachable rows` ` ` `# from the current row` ` ` `mx1 ` `=` `-` `1` ` ` `# Stores the count of cell that are` ` ` `# reachable from the current row` ` ` `cont1 ` `=` `0` ` ` `i ` `=` `0` ` ` `while` `(i < s ` `and` `i < n):` ` ` `# Count of reachable rows` ` ` `aux ` `=` `(n ` `-` `(i ` `+` `1` `)) ` `/` `/` `s ` `+` `1` ` ` `# Update the maximum value` ` ` `if` `(aux > mx1):` ` ` `mx1 ` `=` `cont1 ` `=` `aux` ` ` `# Add it to the count` ` ` `elif` `(aux ` `=` `=` `mx1):` ` ` `cont1 ` `+` `=` `aux` ` ` `i ` `+` `=` `1` ` ` `# Maximum reachable columns from` ` ` `# the current column` ` ` `mx2 ` `=` `-` `1` ` ` `# Stores the count of cell that are` ` ` `# reachable from the current column` ` ` `cont2 ` `=` `0` ` ` ` ` `i ` `=` `0` ` ` `while` `(i < s ` `and` `i < m):` ` ` `# Count of rechable columns` ` ` `aux ` `=` `(m ` `-` `(i ` `+` `1` `)) ` `/` `/` `s ` `+` `1` ` ` `# Update the maximum value` ` ` `if` `(aux > mx2):` ` ` `mx2 ` `=` `cont2 ` `=` `aux` ` ` `# Add it to the count` ` ` `elif` `(aux ` `=` `=` `mx2):` ` ` `cont2 ` `+` `=` `aux` ` ` `i ` `+` `=` `1` ` ` `# Return the total count of cells` ` ` `return` `cont1 ` `*` `cont2` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `N ` `=` `5` ` ` `M ` `=` `5` ` ` `K ` `=` `2` ` ` `print` `(countCells(N, M, K))` ` ` ` ` `# This code is contributed by ipg2016107` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG{` `// Function to count the number of cells` `// in the grid such that maximum cell is` `// reachable with a jump of K` `static` `int` `countCells(` `int` `n, ` `int` `m, ` `int` `s)` `{` ` ` ` ` `// Maximum reachable rows` ` ` `// from the current row` ` ` `int` `mx1 = -1;` ` ` `// Stores the count of cell that are` ` ` `// reachable from the current row` ` ` `int` `cont1 = 0;` ` ` `for` `(` `int` `i = 0; i < s && i < n; ++i) {` ` ` `// Count of reachable rows` ` ` `int` `aux = (n - (i + 1)) / s + 1;` ` ` `// Update the maximum value` ` ` `if` `(aux > mx1) {` ` ` `mx1 = cont1 = aux;` ` ` `}` ` ` `// Add it to the count` ` ` `else` `if` `(aux == mx1)` ` ` `cont1 += aux;` ` ` `}` ` ` `// Maximum reachable columns from` ` ` `// the current column` ` ` `int` `mx2 = -1;` ` ` `// Stores the count of cell that are` ` ` `// reachable from the current column` ` ` `int` `cont2 = 0;` ` ` `for` `(` `int` `i = 0; i < s && i < m; ++i) {` ` ` `// Count of rechable columns` ` ` `int` `aux = (m - (i + 1)) / s + 1;` ` ` `// Update the maximum value` ` ` `if` `(aux > mx2)` ` ` `mx2 = cont2 = aux;` ` ` `// Add it to the count` ` ` `else` `if` `(aux == mx2)` ` ` `cont2 += aux;` ` ` `}` ` ` `// Return the total count of cells` ` ` `return` `(cont1 * cont2);` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `N = 5, M = 5, K = 2;` ` ` `Console.Write(countCells(N, M, K));` `}` `}` `// This code is contributed by ipg2016107.` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to count the number of cells` `// in the grid such that maximum cell is` `// reachable with a jump of K` `function` `countCells(n, m, s)` `{` ` ` `// Maximum reachable rows` ` ` `// from the current row` ` ` `let mx1 = -1;` ` ` `// Stores the count of cell that are` ` ` `// reachable from the current row` ` ` `let cont1 = 0;` ` ` `for` `(let i = 0; i < s && i < n; ++i) {` ` ` `// Count of reachable rows` ` ` `let aux = Math.floor((n - (i + 1)) / s + 1);` ` ` `// Update the maximum value` ` ` `if` `(aux > mx1) {` ` ` `mx1 = cont1 = aux;` ` ` `}` ` ` `// Add it to the count` ` ` `else` `if` `(aux == mx1) cont1 += aux;` ` ` `}` ` ` `// Maximum reachable columns from` ` ` `// the current column` ` ` `let mx2 = -1;` ` ` `// Stores the count of cell that are` ` ` `// reachable from the current column` ` ` `let cont2 = 0;` ` ` `for` `(let i = 0; i < s && i < m; ++i) {` ` ` `// Count of rechable columns` ` ` `let aux = Math.floor((m - (i + 1)) / s + 1);` ` ` `// Update the maximum value` ` ` `if` `(aux > mx2) mx2 = cont2 = aux;` ` ` `// Add it to the count` ` ` `else` `if` `(aux == mx2) cont2 += aux;` ` ` `}` ` ` `// Return the total count of cells` ` ` `return` `cont1 * cont2;` `}` `// Driver Code` `let N = 5,` ` ` `M = 5,` ` ` `K = 2;` `document.write(countCells(N, M, K));` `// This code is contributed by gfgking.` `</script>` |

**Output:**

9

**Time Complexity:** O(N + M)**Auxiliary Space:** O(1)