Header Ads Widget

Maximum borders | Hackerearth solutions

 Program :-

You are given a table with n rows and m columns. Each cell is colored with white or black. Considering the shapes created by black cells, what is the maximum border of these shapes? Border of a shape means the maximum number of consecutive black cells in any row or column without any white cell in between.

A shape is a set of connected cells. Two cells are connected if they share an edge. Note that no shape has a hole in it.

Input format

  • The first line contains t denoting the number of test cases.
  • The first line of each test case contains integers n, m denoting the number of rows and columns of the matrix. Here, '#' represents a black cell and '.' represents a white cell. 
  • Each of the next n lines contains m integers.

Output format

Print the maximum border of the shapes.

Sample Input
10
2 15
.....####......
.....#.........
7 9
...###...
...###...
..#......
.####....
..#......
...#####.
.........
18 11
.#########.
########...
.........#.
####.......
.....#####.
.....##....
....#####..
.....####..
..###......
......#....
....#####..
...####....
##.........
#####......
....#####..
....##.....
.#######...
.#.........
1 15
.....######....
5 11
..#####....
.#######...
......#....
....#####..
...#####...
8 13
.....######..
......##.....
########.....
...#.........
.............
#######......
..######.....
####.........
7 5
.....
..##.
###..
..##.
.....
..#..
.#...
14 2
..
#.
..
#.
..
#.
..
..
#.
..
..
..
#.
..
7 15
.###########...
##############.
...####........
...##########..
.......#.......
.....#########.
.#######.......
12 6
#####.
###...
#.....
##....
###...
......
.##...
..##..
...#..
..#...
#####.
####..
Sample Output
4
5
9
6
7
8
3
1
14
5
Time Limit: 1
Memory Limit: 256
Source Limit:




Code(c++):-

#include <bits/stdc++.h>
using namespace std;
#define ed '\n'
#define gp ' '
#define ll long long int
#define vec vector
#define str string
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7;
const int inf = 1e9;
bool solve()
{
int n, m, i, start, end, ans = INT_MIN;
cin >> n >> m;
string line;
while (n--)
{
cin >> line;
for (i = 0; i < m; i++)
{
if (line[i] == '#')
break;
}
start = i;
for (; i < m; i++)
{
if (line[i] == '.')
break;
}
end = i;
ans = max(ans, end - start);
}
cout << ans << ed;
return true;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
solve();
return 0;
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-