Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AI_ZZ - Zig Zag

Hay un rumor de que en tu ciudad existe un tesoro enterrado desde hace siglos. Muchas personas venden mapas diciendo que te llevara directo al tesoro, lamentablemente no puedes saber si un mapa es verdadero o falso pero existe otra curiosidad más, se dice que el camino al tesoro tiene forma de zig zag.

Como deseas encontrar el tesoro mas antes que otros has comprado todos los distintos mapas que están a la venta, pero son realmente muchos, tu tarea es identificar que mapas contienen un camino con forma de zig zag.

Entrada

Un mapa se ha divido en pequeños sectores cuadrados, por lo tanto tienes como entrada dos números enteros n y m (3 ≤ n, m ≤ 100) y (n ≤ m), donde n es el alto total del mapa y m el el ancho total del mapa. Luego n filas siguen conteniendo m números donde 0 representa la ausencia de un camino y 1 la presencia de un camino en el mapa, un camino puede estar unido de forma vertical horizontal y diagonal.

Salida

Imprimir 'YES' si el camino tiene forma de zig zag y recorre todo el mapa empezando siempre desde la esquina superior izquierda, caso contrario imprimir 'NO'.

Ejemplo

Input:
3 10
1 0 0 0 1 0 0 0 1 0
0 1 0 1 0 1 0 1 0 1
0 0 1 0 0 0 1 0 0 0

Output:
YES

Input:
3 5
0 1 0 0 0
0 0 1 0 1
0 0 0 1 0


Output:
NO

Input:
3 5
1 1 1 0 1
0 1 0 1 0
1 0 1 0 0

Output:
YES

Input:
3 3
0 0 0
1 1 1
0 0 0

Output:
NO

Input:
3 9
1 0 0 0 0 0 0 0 1
0 1 0 1 0 1 0 1 0
0 0 1 0 1 0 1 0 0
Output:
NO

Adicionado por:Hernan Payrumani
Fecha:2013-09-14
Tiempo límite:1s
Límite del código fuente:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Lenguajes:C CSHARP CPP C++ 4.3.2 JAVA
Fuente:Abierto de Informática Ronda 1

ocultar comentarios
2015-03-27 04:59:56 Yovani Zuñiga
altepaco una condicion es tambien que empieze a[0,0] el camino
2014-09-29 09:58:51 Yovani Zuñiga
en el ultimo ejemplo hay un cero en el camino
2014-08-20 18:03:54 alepaco
que pasa con este caso ?
[0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 1 0]
[1 0 0 0 0 1 0 0]
[0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0]
[0 0 0 1 0 0 0 0]




Última edición: 2014-08-20 18:14:33
2013-12-03 07:24:24 thextroid
[0 1 0] [1 0 1] [1 0 0]
[1 0 1] [0 1 0] [0 1 0]
[0 1 0] [1 0 1], [0 0 1], son validos estos caminos?


Última edición: 2013-12-03 07:31:27
2013-12-03 04:23:45 thextroid
supongo q el ultimo ejemplo... es xq no va en zig zag hasta el tope de arriba y hasta el tope de abajo ... pienso q debe cumplir ese requisito...
2013-11-26 03:58:45 Miguel Figueira
xq el último ejemplo da NO?? yo veo que cumple con las condiciones..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.