Carré – Épreuve régionale 2011

Niveau 4

Énoncé

On se trouve dans un monde étrange, où la terre est un carré de taille N × N. Le monde est sous l'eau ; on ne peut se déplacer que vers le bas ou la droite à cause du courant. De plus, des obstacles occupent certaines cases et empêchent donc d'y passer.

Le but du jeu est de trouver le nombre de chemins entre la case (0, 0) et la case (N - 1, N - 1).

Entrée

  • Sur la première ligne, l'entier N.
  • Sur les N lignes suivantes, une liste de N « 1 » ou « 0 » (1 représente un vide et 0 un obstacle).

Sortie

Soit X, le nombre de chemins distincts. Votre programme devra en imprimer les 6 derniers chiffres.

Contraintes

  • 1 <= N <= 1 000

Contraintes d'exécution

Utilisation mémoire maximum
10240 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
1 1 1
1 0 1
1 1 1
Exemple de sortie
2
Exemple d'entrée
4
1 1 1 1
1 0 1 1
1 1 1 1
1 1 1 1
Exemple de sortie
8