中南大学2012年8月月赛Problem E: Enjoy treasure 3维迷宫
服务器仍在调整，OJ目前可以访问，但未打开判题端。
SUBMIT: 24 Solved: 6
[SUBMIT][STATUS]
GBQC国最伟大的发明就是时空穿梭机，有了它，任何交通工具都是浮云，它可以把你传送到任何你想去的地方。但是牛B的东西一般都是有BUG的。
一天，小明本来想传到小红家去，也许是最近探险小说看多了，脑子里总是想着宝藏，结果他被传送到了一个大山洞中。这个大山洞有N层，每层都由M*M个小山洞组成，有的小山洞有通往上一层或者下一层的楼梯，有的小山洞中藏有宝物。小明突然发现这个大山洞是那么的眼熟，这竟和小说中描述的神秘洞穴一模一样，山洞中的宝物都是稀世珍宝！但现在更重要的是，小明要从这个充满危险和财富的山洞中逃跑出去。小明传送进来的那一刻，已经触发了山洞的机关，山洞的底部开始漫水，并且水每K秒都会向上漫一层。而小明每秒都只能移动到四周的山洞或者通过楼梯走到上下层的山洞，小明走过的地方都会长出荆棘，无法返回。小明想要逃出这个山洞，同时，他又想拿到更多的宝物。请你帮小明设计一条路线，让小明活着走出山洞并拿到尽量多的宝物。
Input输入包含多组测试数据。
每组数据第一行包含两个整数N(1<=N<=10)、M(1<=M<=10)、K(1<=K<=2)，表示山洞一共有N层，每层有M*M个小山洞，水每K秒都会向上漫一层。接下来有N个M*M的矩阵，分别表示山洞的1~N层的平面图。第一层是山洞的最高层，上面就地面。
矩阵中包含以下字符：
'S'：表示小明的位置，有且只有一个。
'*'：表示一个小山洞，可以随意通行。
'#'：表示一个放有宝物的小山洞。
'U'：表示一个放有向上梯子的山洞，这个山洞中你可以选择是否进到上一层。(约10%)
'D'：表示一个放有向下梯子的山洞，这个山洞中你可以选择是否进到下一层。(约10%)
水一开始在山洞底部，第K秒就会漫掉山洞的第N层，并且每K秒都会向上漫一层。小明只有从第1层出来到达地面，才能算逃离了山洞。
Output如果小明能逃出山洞，输出它能拿到的最多的宝物数。如果小明不能逃出山洞，输出-1。
Sample Input/*剪枝搜索，预处理到出口的最短路，放弃无法逃出和立刻被淹的点。 */#include<stdio.h>#include<stdlib.h>#include<string.h>#include<queue>using namespace std;const int maxn = 11;const int inf = 0x3f3f3f3f;struct node{int x, y, z, pace;node(){}node(int a, int b, int c, int d){x = a, y = b, z = c, pace = d;}};char g[maxn][maxn][maxn];int dis[maxn][maxn][maxn];int n, m, K, sx, sy, sz;int dx[6] = {-1, 1, 0, 0, 0, 0};int dy[6] = {0, 0, -1, 1, 0, 0};int dz[6] = {0, 0, 0, 0, -1, 1};int ans;bool BFS(){memset(dis, 0x3f, sizeof(dis));int i, j, nx, ny, nz;queue<node> q;node lin, nex;for(i = 1; i <= m; ++ i)for(j = 1; j <= m; ++ j)if(g[1][i][j] == 'U') q.push(node(1, i, j, 1)), dis[1][i][j] = 1;//从第一层开始如果遇到up就是最短路为1while(!q.empty()){lin = q.front(), q.pop();for(i = 0; i < 6; ++ i){if(g[lin.x + 1][lin.y][lin.z] != 'U' && i == 1) continue;//当i==1的时候 只有当其下一层为up的时候才能上来(即才能nex.x=lin.x+1)if(g[lin.x - 1][lin.y][lin.z] != 'D' && i == 0) continue;//因为我们是倒推的 求最短路是倒推出来的 当i等于1 只有当下一层是upnex.x = lin.x + dx[i]; //的时候才能走到当前状态 所以从当前状态推出上一个状态，上个状态最短路要加1 nex.y = lin.y + dy[i];nex.z = lin.z + dz[i];if(g[nex.x][nex.y][nex.z] && dis[nex.x][nex.y][nex.z] == inf)nex.pace = lin.pace + 1, dis[nex.x][nex.y][nex.z] = nex.pace, q.push(nex);}}return dis[sx][sy][sz] <= n * K;}bool vis[maxn][maxn][maxn];bool flag;void DFS(int x, int y, int z, int now, int cnt)//now是剩余时间{int nx, ny, nz, i;if(x == 1 && g[x][y][z] == 'U'){ flag = true; if(cnt > ans) ans = cnt;}if(g[x][y][z] == '#') ++ cnt;for(i = 0; i < 6; ++ i){if(g[x][y][z] != 'U' && i == 0) continue;if(g[x][y][z] != 'D' && i == 1) continue;nx = x + dx[i];ny = y + dy[i];nz = z + dz[i];if(g[nx][ny][nz] && !vis[nx][ny][nz] && dis[nx][ny][nz] < now && n - (K * n - now + 1) / K >= nx)//还剩下的时间能走的层数如果大于nx 则继续{ vis[nx][ny][nz] = true;DFS(nx, ny, nz, now - 1, cnt); vis[nx][ny][nz] = false;}}}int main(){int i, j, k;//freopen("E1.in", "rb", stdin);//freopen("EEE1.out", "wb", stdout);while(scanf("%d%d%d", &n, &m, &K) != EOF){memset(g, 0, sizeof(g));for(i = 1; i <= n; ++ i)for(j = 1; j <= m; ++ j){scanf("%s", g[i][j] + 1);for(k = 1; k <= m; ++ k)if(g[i][j][k] == 'S')sx = i, sy = j, sz = k;}if(BFS()){ans = flag = 0;memset(vis, 0, sizeof(vis));vis[sx][sy][sz] = true;DFS(sx, sy, sz, K * n, 0);if(flag) printf("%d\n", ans); else printf("-1\n");}else printf("-1\n");}return 0;}