Home » Interview coding problems/challenges

# Find the perfect land of C shape

Here, we are going to learn **how to find the perfect land of a C shape**? There is an area of size N*M and each point of N*M has a value. But he wants exactly a land of size 3*3 but the land should be perfect.

Submitted by Debasis Jana, on April 21, 2019

**Problem Statement:**

Debasis is searching for a **perfect land to build a new house**. There is an area of size **N*M** and each point of **N*M** has a value. But he wants exactly a **land of size 3*3 but the land should be perfect**.

A **perfect land is a land whose 'C' shape value is maximum**.

You being his friend, help him to find the perfect land.

**Input**

First line of the input is two space separated integer **N** and **M**

Second line of the input contains the matrix of size **N*M** (**N** rows **M** columns).

**Output**

A single integer containing the sum of the perfect land.

**Example:**

Input: 6 6 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Output: 7

**Explanation:**

Here is **the perfect land whose sum value is maximum**.

**Note:** Before going to solution please try it by yourself.

**C++ implementation:**

#include <bits/stdc++.h> #define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL) using namespace std; int main() { FASTIO; //Taking Fast Input Output int n,m,x; cin>>n>>m; //taking input n and m int arr[n][m]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { //taking input for the matrix cin>>arr[i][j]; } } //it will store the maximum value of the perfect land int max1=0; for(int i=0;i<n-2;i++) { for(int j=0;j<m-2;j++) { //it will calclute the total sum of each C shape land int sum1=0; //here we are calculating the sum of each C shape //land of size 3*3 //this is for first line of C shape sum1=sum1+arr[i][j]+arr[i][j+1]+arr[i][j+2]; //second line of C shape sum1+=arr[i+1][j]; //3rd line of C shape sum1+=arr[i+2][j]+arr[i+2][j+1]+arr[i+2][j+2]; //checking if the sum is grater than //the previous C shape land if(sum1>=max1) max1=sum1; } } cout<<max1<<"\n"; return 0; }

**Output**

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.