題意：有8個立方體，按相同顏色著色，相對面是相同顏色，按同一方向擺成3*3的方陣。問從初始狀態(tài)到目標狀態(tài)最少移動步數(shù)。

分析：題目是最短路徑題，可以bfs可以回溯，用回溯加剪枝。不能走的格子是上次走的空格。

# include<iostream> # include<cstdio> # include<cmath> # include<map> # include<queue> # include<cstring> #include<set> # include<algorithm> using namespace std;struct node {int top, front; }; int goal[3][3]; node start[3][3]; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; int step = 31; int judge() {int t = 0;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (start[i][j].top != goal[i][j])t++;}}return t; } void move(int x,int y,int i) {int ddx = x + dx[i]; int ddy = y + dy[i];if (i == 0 || i == 1) {swap(start[x][y].front, start[x][y].top);}else {start[x][y].top = 1 ^ 2 ^ 3 ^ start[x][y].front^start[x][y].top;}swap(start[x][y], start[ddx][ddy]); } void dfs(int curx,int cury,int layer) {if (layer > 30)return;int jp = judge();if (jp==0) {step = min(step, layer);return;}if (jp + layer > step)return;//剪枝int tx, ty;for(int i=0;i<3;i++)for(int j=0;j<3;j++)if (!start[i][j].top) {tx = i; ty = j; break;}for (int i = 0; i < 4; i++) {int ddx = tx + dx[i];int ddy = ty + dy[i];if (ddx >= 0 && ddx < 3 && ddy>=0 && ddy < 3 && (ddx != curx || ddy != cury)) {move(ddx, ddy, i ^ 1);dfs(tx, ty, layer + 1);move(tx, ty, i);}} } int main() {int ex, ey;char k;//0-empty,1-red,2-blue,3-whitewhile (cin >> ey >> ex && ex&&ey) {ex--; ey--;step = 31;for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++) {cin >> k;if (k == 'E')goal[i][j] = 0;else if (k == 'W')goal[i][j] = 3;else if (k == 'R')goal[i][j] = 1;else if (k == 'B')goal[i][j] = 2;if (ex == i && ey == j) {start[i][j].front = 0; start[i][j].top = 0;}else {start[i][j].front = 1; start[i][j].top = 3;}}dfs(-1, -1, 0);step = step > 30 ? -1 : step;cout << step << endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的UVA - 1604Cubic Eight-Puzzle立体八数码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。