سؤال برنامه نویسی: بازی مسیرهای ممنوعه

توضیح صورت مسئله:

شما در یک صفحه‌ی مربعی به ابعاد n x n هستید (اندیس ردیف‌ها و ستون‌ها از 0 شروع می‌شود).ابتدا در خانه‌ی (0, 0) هستید و می‌خواهید به خانه‌ی (n-1, n-1) بروید.

• فقط مجازید به سمت راست یا پایین حرکت کنید.

• یکسری از خانه‌ها ممنوعه هستند و نمی‌توانید روی آن‌ها قدم بگذارید.

هدف شما محاسبه‌ی تعداد مسیرهای ممکن از (0,0) تا (n-1,n-1) است بدون اینکه وارد خانه‌های ممنوعه شوید.

ورودی:

1. عدد صحیح n (ابعاد صفحه) (1 ≤ n ≤ 20)

2. عدد صحیح k (تعداد خانه‌های ممنوعه) (0 ≤ k ≤ n*n)

3. k خط بعدی، هر کدام شامل دو عدد r و c که مختصات یک خانه‌ی ممنوعه هستند (0 ≤ r,c < n)

خروجی:

• یک عدد که نشان‌دهنده‌ی تعداد کل مسیرهای مجاز است.

نکات:

• ممکن است هیچ مسیری وجود نداشته باشد (در این صورت خروجی باید 0 باشد).

• اگر خانه‌ی (0,0) یا (n-1,n-1) ممنوع باشد، مستقیماً خروجی صفر است.

نمونه ورودی 1:

3
1
1 1

توضیح:

صفحه:

(0,0) (0,1) (0,2)
(1,0)  X    (1,2)
(2,0) (2,1) (2,2)

(X یعنی ممنوعه)

مسیرهای ممکن:

• (0,0) → (0,1) → (0,2) → (1,2) → (2,2)

• (0,0) → (1,0) → (2,0) → (2,1) → (2,2)

• (0,0) → (1,0) → (2,0) → (2,1) → (1,2) → (2,2) (غیرممکن چون  (1,2) قبل از (2,1) باید بیاد)

جواب:

2

نمونه ورودی 2:

2
2
0 1
1 0

توضیح:

صفحه:

(0,0)  X
 X    (1,1)

هیچ راهی برای حرکت نیست.

جواب:

0