給定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個骨牌。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| using namespace std; | |
| int N, M; | |
| int i1, i2, d1, d2, p[20], q[20]; | |
| int choosed[20]; | |
| bool backtracking(int Len, int num) | |
| { | |
| if (Len == N) { | |
| if (num == d1) return true; | |
| return false; | |
| } | |
| for (int i = 0; i < M; ++i) { | |
| if (choosed[i]) continue; | |
| if (p[i] == num || q[i] == num) { | |
| choosed[i] = 1; | |
| bool ok; | |
| if (p[i] == num) ok = backtracking(Len + 1, q[i]); | |
| else ok = backtracking(Len + 1, p[i]); | |
| if (ok) return true; | |
| choosed[i] = 0; | |
| } | |
| } | |
| return false; | |
| } | |
| int main() | |
| { | |
| while (scanf("%d %d", &N, &M) && N) { | |
| scanf("%d %d %d %d", &i1, &i2, &d1, &d2); | |
| for (int i = 0; i < M; ++i) { | |
| scanf("%d %d", &p[i], &q[i]); | |
| choosed[i] = 0; | |
| } | |
| if (backtracking(0, i2)) puts("YES"); | |
| else puts("NO"); | |
| } | |
| return 0; | |
| } |
沒有留言:
張貼留言