網頁

2014年3月9日 星期日

UVa 10503 The dominoes solotarie

題意:
    給定N表示起點和終點之間要填入N個骨牌,給定M表示除了起點和終點外還有M個骨牌,每個骨牌兩端高度不一樣,因此一個骨牌用(p,q)來表示其兩端的高度。在放骨牌的時候,其相鄰的骨牌連接的那端高度需一致(例如一段骨牌放置如(a,b),(b,c),(c,d),(d,e))。起點(i1,i2)和終點(d1,d2)這兩個骨牌的兩端是不能交換的(不能變成(i2,i1)),而其它M個骨牌在放入的時候兩端是能交換的,因此這題要確認是否能在(i1,i2)和(d1,d2)之間放入N個骨牌。

想法:
    用backtracking確認是否能在起點和終點間放入N個骨牌。