e431: 不交錯一筆走完
Tags : DFS
Accepted rate : 21人/23人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-11 08:52

Content

假設現在平面上有水平m個點,垂直n個格點,要一筆將這些格點全部連起來

每個格點只能跟自己前,後,左,右的格點以直線相連,而且規定直線不能相交(同一個格點不能經過2次以上,起點也不能是終點)

舉例來說:

如果m=4,n=3:

格點由上而下,由左而右是從(1,1)~(m,n)

(1,1)->(1,2)->(1,3)->(2,3)->(2,2)->(2,1)->(3,1)->(3,2)->(3,3)->(3,4)->(2,4)->(1,4)是一個合法路徑

(1,4)->(2,4)->(3,4)->(3,3)->(3,2)->(3,1)->(2,1)->(2,2)->(2,3)->(1,3)->(1,2)->(1,1)也算是同一個合法路徑(只有起點和終點對調)

(2,2)->(2,1)->(1,1)->(1,2)->(1,3)->(2,3)->(2,2)->(3,2)->(3,1)->(4,1)->(4,2)->(4,3)->(3,3)->(3,2)是一個非法路徑((2,2)和(3,3)都經過了2次)

現在給你 m,n ,求出總共有多少合法路徑

Input

多筆測資

一行有兩個正整數m,n(m+n<12)

Output

合法路徑數

Sample Input
5 4
Sample Output
1006
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 0.1s , <1K
公開 測資點#2 (20%): 0.1s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 2.2s , <1K
Hint :

只有起點和終點對調,連線的位置與路徑都一樣時,算是同一種路徑

如果上下或左右翻轉後,只是形狀相同,但位置不同,則算是不同的路徑

 

Tags:
DFS
出處:
π [管理者:
314159265358979... (少年π)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」