시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 6 | 0 | 0 | 0.000% |
NxNの方眼がある。
(N=3の場合の図)
隣接するマス目に移動するにはコストが1かかる。ただし、斜めに移動することは出来ない。 また障害物があるマス目がM個あり、そのマスに入ることは許されない。 マス(1, 1)からマス(N, N)に最小のコストで移動する方法は何通りあるか。 答えは大きくなることがありうるので、1000000009(=109+9)でMODを取って出力せよ。
入力は以下の形式で与えられる
N M X1 Y1 X2 Y2 …… XM YM
Xi, Yiは(Xi, Yi)に障害物があることを表す
1行に経路の総数を出力せよ。ただし、マス(1, 1)からマス(N, N)に移動する経路が存在しない場合は0と出力せよ。
2 ≤ N ≤ 106
0 ≤ M ≤ 50
1 ≤ Xi , Yi ≤ N
i ≠ jならば (Xi, Yi) ≠ (Xj, Yj)
(Xi, Yi) ≠ (1, 1)
(Xi, Yi) ≠ (N, N)
3 0
6
以下の図に対応する。
3 1 2 2
2
以下の図に対応する。
5 8 4 3 2 1 4 2 4 4 3 4 2 2 2 4 1 4
1
以下の図に対応する。
1000 10 104 87 637 366 393 681 215 604 707 876 943 414 95 327 93 415 663 596 661 842
340340391
2 2 1 2 2 1
0