d821: 最短路徑個數
Tags : BFS DP
Accepted rate : 79人/98人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-04-04 18:26

Content

地圖上,由 ( Sx , Sy )只能上下左右到達 ( Ex , Ey ) 的最短路徑長

想必大家都已經不陌生了,那麼現在請寫出

( Sx , Sy )→ ( Ex , Ey )  的最短路徑個數

Input

每組測資,第一行有兩個整數 N M ( 1 ≦ N , M ≦ 50 )

接下來會有 N 行

每行上分別有 M 個 0 1 構成的地圖

0 代表可以通行,1 代表有障礙物

接下來還會有一行有四個數字,Sx , Sy , Ex , Ey

0≦ Sx , Ex < N, 0 ≦ Sy , Ey < M

左上角為 ( 0 , 0 ) ,右下角為 ( N-1 , M-1 )

 

Output
答案可能很大,請輸出 mod 100000 後的結果
Sample Input #1
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 4 4
6 5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 0 1 1 0
0 1 1 0 0
0 0 0 0 0
0 4 5 0
6 5
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0
0 4 5 0
Sample Output #1
70
3
6
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (70%): 1.0s , <1M
公開 測資點#1 (30%): 1.0s , <1K
Hint :
Tags:
BFS DP
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
23911 d821
272 2021-01-01 01:40