Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2450
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2450
Matrix Ladder
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");
}
Input
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
#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;
}
Input
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