50125. Consecutive 1’s with Function

I'm a slow walker, but I never walk backwards.

Task Description

We have a two-dimensional array. The size of the array is $N$ by $N$. Each element of the array is either 0 or 1.

Write a function to compute the length of the longest continuous “1” along a row, along a columns, or along a diagonal directional. You need to consider both diagonal directions, as shown in the figure below.

samplesample

The First Subtask (50%)

In the first subtask you will write a function findLength to help us. The prototype of this function findLength is as follow:

int findLength (int array[][256], int N, int r, int c, int dr, int dc);

The function findLength returns the maximum length of consecutive 1's that we can find from the $r$-th row and the $c$-th column in the direction of ($dr$, $dc$) in an $N$ by $N$ array. Note that the segment of the maximum lenght of consecutive 1's does not necessarily start from $(r, c)$.

We will use the following main program to test your function. You can download it and name it mainTest.c to help test your findLength.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include "findLength.h"
#define MAXN 256
int main () {
    int array[MAXN][MAXN];
    int N, r, c;
    int direction[4][2] = {{1,0}, {1,1}, {0,1}, {-1,1}};
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%d", &array[i][j]);
    scanf("%d%d", &r, &c);
    for (int i = 0; i < 4; i++)
        printf("%d\n", findLength(array, N, r, c, direction[i][0], direction[i][1]));
}

Compile

You can compile your findLength.c and our mainTest together by the following command.

1
gcc -O2 mainTest.c findLength.c

Input Format

In the first subtasks the first line has an integer $N$, which is the size of the array. The next $N$ lines have $N$ integers, which are either 1 or 0. They are elements of the array. At the end there are two integer $r$ and $c$, where ($r$, $c$) is the position to test findLength.

  • $1\leq N\leq 256$

Output Format

For the first subtask, there are four lines in the output. Each line has one integer that is the length of consecutive “1” in that direction.

Sample Input 1

5
1 0 1 1 0
1 0 0 1 1
0 1 1 1 1
0 1 1 0 1
0 1 0 1 1
3 1

Sample Output 1

2
1
2
3

The Second Subtask (50%)

In the second task you need to implement your main program (main.c) to find the maximum length of consecutive 1's by calling your findLength function.

Input Format

This is the same as in the first subtask except that it does not have $r$ and $c$ at the end.

Output Format

Output the maximum length of consecutive 1 in the array.

Compile

We will test your programs by the following.

1
gcc -O2 main.c findLength.c

Sample Input 2

5
1 0 1 1 0
1 0 0 0 1
0 1 1 1 1
0 1 0 0 1
0 0 0 1 0

Sample Output 2

4

Attention

You must submit two source files.

If you only complete findLength.c, you can submit your main.c as follow.

1
2
int main(){
}

Discussion