Problem
You are given a table with rows and 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
- 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 #####. ###... #..... ##.... ###... ...... .##... ..##.. ...#.. ..#... #####. ####..
My solution
#include <stdio.h>
#include <stdbool.h>
int main(){
int numDataSets,numRows,numCols,maxPatternSize;
bool patternStarted = false;
// Dynamic heap arrays
char *rowDataPtr;
int *rowWisePatternLengthsPtr;
int *dataSetWisePatternLengthsPtr;
scanf("%d", &numDataSets); // Reading number of data sets
//printf("Number of data sets is %d.\n", numDataSets);
// Create an integer array to print all the row wise pattern lengths at the end
dataSetWisePatternLengthsPtr = (int*) malloc (numDataSets * sizeof(int));
for (int i=0;i<numDataSets;i++)
{
//printf("\n==========================================");
//printf("\nData set = %d",i);
// Get number of rows and cols in each data set
scanf("%d", &numRows );
//printf("\nNumber of rows in this data set %d is %d",i, numRows);
scanf("%d", &numCols );
//printf("\nNumber of Cols in this data set %d is %d",i, numCols);
// Create an integer array to print all the row wise pattern lengths at the end
rowWisePatternLengthsPtr = (int*) malloc (numRows * sizeof(int));
//Take in one row of the data at a time.
for (int rowNum=0;rowNum<numRows;rowNum++)
{
//printf("\n Row number = %d : ", rowNum );
patternStarted = false;
rowWisePatternLengthsPtr[rowNum] = 0;
// In each row, assume that the pattern has not started and pattern length is 0
// Create a char array dynamically on the heap
// Adding 1 so that new line can be stored?
rowDataPtr = (char*) malloc ((numCols+1)*sizeof(char));
if (rowDataPtr == NULL)
{
printf("\n Could not allocate the memory for row %d",rowNum);
printf("\n Required column size = %d",numCols);
}
// Scan all characters of the row
for (int colNum=0;colNum<=numCols;colNum++)
{
scanf("%c", &rowDataPtr[colNum] );
//printf("\n Column number %d is %c", colNum,rowDataPtr[colNum] );
}
// Print all characters of the row for checking
for (int colNum=0;colNum<=numCols;colNum++)
{
//printf("%c", rowDataPtr[colNum] );
}
for (int colNum=0;colNum<=numCols;colNum++)
{
if ((rowDataPtr[colNum] == '#') && (colNum != numCols))
{
patternStarted = true;
rowWisePatternLengthsPtr[rowNum]++;
}
if ((rowDataPtr[colNum] == '.') && (patternStarted == true))
{
patternStarted = false;
break;
}
}
//printf("Row wise length = %d\n",rowWisePatternLengthsPtr[rowNum]);
}
// Find the maximum number of stars in the array rowWisePatternLengthsPtr for this data set
maxPatternSize = 0;
for (int rowNum=0;rowNum<numRows;rowNum++)
{
if (rowWisePatternLengthsPtr[rowNum] > maxPatternSize)
{
maxPatternSize = rowWisePatternLengthsPtr[rowNum];
}
}
dataSetWisePatternLengthsPtr[i]=maxPatternSize;
}
for (int i=0;i<numDataSets;i++)
{
//printf("\ndata set num %d= %d",i,dataSetWisePatternLengthsPtr[i]);
printf("\n%d",dataSetWisePatternLengthsPtr[i]);
}
}
No comments:
Post a Comment