Maximum borders
Practice
2.4 (537 votes)
Basic programming
Input/output
Problem
65% Success 66282 Attempts 20 Points 1s Time Limit 256MB Memory 1024 KB Max Code
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
Explanation
-
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Submissions
Please login to view your submissions
Similar Problems
Points:30
16 votes
Tags:
AlgorithmsApprovedGraphsMediumOpenTrees
Points:20
772 votes
Tags:
Ad-HocBasic ProgrammingEasy
Points:20
15 votes
Tags:
EasyMathSorting
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor