題目大意：有n個正方體，從序號1~n， 對應的每個立方體的6個面分別有它的顏色（用數字給出），現在想要將立方體堆成塔，并且上面的立方體的序號要小于下面立方體的序號，相鄰的面顏色必須相同。輸出最高值和路徑。
解題思路：因為立方體可以旋轉，所以一個序號的立方體對應這6種不同的擺放方式，可以將問題理解成DAG最長路問題， 只是搜索范圍是從i + 1開始到n。然后記錄路徑要開兩個2維數組。
路徑不唯一，隨便輸出一條。
?
#include <stdio.h>
#include <string.h>
const int N = 1005;
const int M = 10;
const char sign[M][10]= {"front", "back", "left", "right", "top", "bottom"};
struct state {
int in;
int out;
}tmp[N][M];
int n, x[N][M], y[N][M], dp[N][M];
void Init() {
memset(tmp, 0, sizeof(tmp));
memset(dp, 0, sizeof(dp));
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
}
void write(int k, int a, int b, int d) {
tmp[d][k].in = a;
tmp[d][k].out = b;
}
void read() {
int a, b;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) {
scanf("%d%d", &a, &b);
write(j * 2, a, b, i);
write(j * 2 + 1, b, a, i);
}
}
}
int search(int d, int k) {
if (dp[d][k]) return dp[d][k];
for (int i = d + 1; i <= n; i++) {
for (int j = 0; j < 6; j++) {
if (tmp[i][j].in == tmp[d][k].out) {
int a = search(i, j);
if (a > dp[d][k]) {
dp[d][k] = a;
x[d][k] = i, y[d][k] = j;
}
}
}
}
return ++dp[d][k];
}
void solve() {
int Max = 0, idx, idy, a;
for (int i = 1; i <= n; i++) {
if (Max + i >= n) break;
for (int j = 0; j < 6; j++) {
a = search(i, j);
if (a > Max) {
Max = a;
idx = i, idy = j;
}
}
}
printf("%d\n", Max);
for (int i = 0; i < Max; i++) {
printf("%d %s\n", idx, sign[idy]);
a = idx;
idx = x[idx][idy];
idy = y[a][idy];
}
/*
printf("%d\n", dp[1][5]);
idx = 1; idy = 5;
for (int i = 0; idx; i++) {
printf("%d %s\n", idx, sign[idy]);
a = idx;
idx = x[idx][idy];
idy = y[a][idy];
}
*/
}
int main() {
int cas = 0;
while (scanf("%d", &n), n) {
Init();
read();
if (cas) printf("\n");
printf("Case #%d\n", ++cas);
solve();
}
return 0;
}
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
