## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 2450

By OBI - Olimpíada Brasileira de Informática 2014 Brazil

Timelimit: 1

Joaozinho is learning about arrays. Today he learned how to make arrays on the ladder shape, and exercising. To help him, you should write a program that determines if the result of it really is in the correct format.

A matrix is ladder shaped when, for each line, the following conditions are met:

• If the line has only zeros, then all rows below it also only have zeros.
• Otherwise, X is nonzero element of the leftmost line; Then, for all the lines below the line X, all elements in the columns left of X and X are zero.

## Input

The first line has two integers N and M (1 ≤ N, M ≤ 500), the dimensions of the matrix. Each of the following N lines contains M (0 ≤ Mij ≤ 105) non-negative integers, the array elements.

## Output

Your program should produce a single line containing the character 'S' if the array is in ladder format, or 'N' otherwise.

 Input Samples Output Samples 4 6 1 2 9 9 9 9 0 0 3 9 9 9 0 0 0 0 5 9 0 0 0 0 0 6 S

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>

#define true 1
#define false 0

int main (void)
{

int ppp = 0;
int c, qtsZeros;
int linha, coluna;
_Bool bo, ok = true;
int qtsLinha, qtsColuna;

scanf("%d %d", &qtsLinha, &qtsColuna);

for (linha = 0; linha  <  qtsLinha; ++linha)
{

qtsZeros = 0;
bo = true;

for (coluna = 0; coluna  <  qtsColuna; ++coluna)
{

scanf("%d", &c);
if (c == 0 && bo)
qtsZeros++;
else
bo = false;

}

if (linha != 0)
{

if ((qtsZeros > ppp || (qtsZeros == ppp && qtsZeros == qtsColuna)) && ok)
ppp = qtsZeros;
else
ppp = 0, ok = false;

}
else
ppp = qtsZeros;

}

if (ppp)
printf("S\n");
else
printf("N\n");

}
``````
Copy The Code &

Input

cmd
4 6
1 2 9 9 9 9
0 0 3 9 9 9
0 0 0 0 5 9
0 0 0 0 0 6

Output

cmd
S

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <cstdio>
int main() {
int ordema, ordemb, i, j;
int numero[500];
scanf("%d %d", &ordema, &ordemb);
for (i = 0; i  <  ordema; i++) {
int anterior = 0, total = 0, jaquebrou = 0;
for (j = 0; j  <  ordemb; j++) {
int davez;
scanf("%d", &davez);
if (davez == 0 && anterior == 0 && jaquebrou == 0)
total++;
else
jaquebrou = 1;
anterior = davez;
}
numero[i] = total;
}
int referencia = numero[0];
for (i = 1; i  <  ordema; i++) {
if (referencia == ordemb) {
if (numero[i] != ordemb) {
printf("N\n");
return 0;
}
} else {
if (numero[i] > referencia)
referencia = numero[i];
else {
printf("N\n");
return 0;
}
}
}
printf("S\n");
return 0;
}
``````
Copy The Code &

Input

cmd
4 6
1 2 9 9 9 9
0 0 3 9 9 9
0 0 0 0 5 9
0 0 0 0 0 6

Output

cmd
S