Carré – Regional event 2011

Level 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

Runtime constraints

Maximum memory usage
10240 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3
1 1 1
1 0 1
1 1 1
Sample output
2
Sample input
4
1 1 1 1
1 0 1 1
1 1 1 1
1 1 1 1
Sample output
8

Submit your solution

You have to register or log in to be able to submit your solution.