problem

luogu-P3342

solution

你感覺這道題沒考什么，又感覺考了什么

通過樣例以及題面，我們并未獲取到『立方體每個小方塊的編號是按一定規則命名』的信息。

也就是說，我們需要通過輸入的每個小方塊相鄰的編號的信息來建出這個立方體的坐標系。

我的做法較暴力但不用思考太多，簡單易上手。你值得擁有

• 首先，我們先隨便找一個三度點（只有三個水晶和該水晶有公共面），欽定為 $(1,1,1)$。

  然后以這個點 $\text{bfs}$ 搜，得到每個點的距離，我們記為 $di{s}_0$。

• 其次，我們再隨便找一個與上一個點距離恰好為 $2n?2$ 的點，即 $di{s}_0(i)=2n?2$，欽定為 $(n,n,1)$。

  然后以這個點 $\text{bfs}$ 搜，得到每個點的距離，我們記為 $di{s}_1$。

• 接著，我們仍隨便找一個與上兩個點距離恰都為 $n?1$ 的點，即 $di{s}_0(i)=di{s}_1(i)=n?1$，欽定為 $(n,1,1)$。

  然后以這個點 $\text{bfs}$ 搜，得到每個點的距離，我們記為 $di{s}_2$。

這里的距離指的是曼哈頓距離 $x,y,z$ 三維坐標差的絕對值之和。

考慮小方塊 $i$ 的距離信息點對 $(di{s}_1(i)?di{s}_0(i),di{s}_2(i)?di{s}_0(i))$。

$\text{observation1}:$ 該點對與 $i$ 的真正的 $z$ 坐標無關。

$\text{observation2}:$ 該點對與小方塊的真正 $(x,y)$ 坐標存在一一對應關系。這只能自己臆想了

而 $di{s}_0(i)=(x,y,z)?(1,1,1)$，所以我們可以選擇通過 $di{s}_0(i)$ 與已經求出的 $x,y$ 來推出小方塊的 $z$ 坐標。

最后只用 $\text{dfs}$ 暴搜枚舉每個特殊發光小水晶擴散的方向，$O(6^n)$。

然后 $\text{check}$ 沿著該方向枚舉一路上的水晶，用 $vis$ 標記是否已經訪問過了，非第一次訪問不計入發光貢獻。

最后清空 $\text{vis}$ 數組，也是按照方向清空。不然就是 $O(a^3)$ 的復雜度了。

時間復雜度 $O(6^{n}a)$。

code

#include <bits/stdc++.h> using namespace std; #define maxn 400000 #define MAX 150 struct node { int x, y, z; }pos[MAX << 2][MAX << 2]; vector < int > G[maxn]; vector < node > NB; int g[maxn], dir[maxn]; int dis[3][maxn]; int vis[MAX][MAX][MAX], val[MAX][MAX][MAX]; int Min = 1e9, Max = -1e9, n, m; queue < int > q;void bfs( int s, int *dis ) {dis[s] = 0; q.push( s );while( ! q.empty() ) {int u = q.front(); q.pop();for( int v : G[u] ) if( dis[v] > dis[u] + 1 ) dis[v] = dis[u] + 1, q.push( v );} }void calc() {int sum = 0;for( int k = 0;k < NB.size();k ++ ) {int x = NB[k].x, y = NB[k].y, z = NB[k].z;switch( dir[k] ) {case 0 : {for( int i = 1;i <= x;i ++ )if( ! vis[i][y][z] )vis[i][y][z] = 1, sum += val[i][y][z];break;}case 1 : {for( int i = x;i <= n;i ++ )if( ! vis[i][y][z] )vis[i][y][z] = 1, sum += val[i][y][z];break;}case 2 : {for( int i = 1;i <= y;i ++ )if( ! vis[x][i][z] )vis[x][i][z] = 1, sum += val[x][i][z];break;}case 3 : {for( int i = y;i <= n;i ++ )if( ! vis[x][i][z] )vis[x][i][z] = 1, sum += val[x][i][z];break;}case 4 : {for( int i = 1;i <= z;i ++ )if( ! vis[x][y][i] )vis[x][y][i] = 1, sum += val[x][y][i];break;}case 5 : {for( int i = z;i <= n;i ++ )if( ! vis[x][y][i] )vis[x][y][i] = 1, sum += val[x][y][i];break;}}}Min = min( Min, sum ), Max = max( Max, sum );for( int k = 0;k < NB.size();k ++ ) {int x = NB[k].x, y = NB[k].y, z = NB[k].z;switch( dir[k] ) {case 0 : for( int i = 1;i <= x;i ++ ) vis[i][y][z] = 0; break;case 1 : for( int i = x;i <= n;i ++ ) vis[i][y][z] = 0; break;case 2 : for( int i = 1;i <= y;i ++ ) vis[x][i][z] = 0; break;case 3 : for( int i = y;i <= n;i ++ ) vis[x][i][z] = 0; break;case 4 : for( int i = 1;i <= z;i ++ ) vis[x][y][i] = 0; break;case 5 : for( int i = z;i <= n;i ++ ) vis[x][y][i] = 0; break;}} }void dfs( int x ) {if( x == NB.size() ) return calc(), void();for( int i = 0;i < 6;i ++ ) dir[x] = i, dfs( x + 1 ); }int CalcDis( int x, int y, int a, int b ) { return fabs( x - a ) + fabs( y - b ); }int main() {memset( dis, 0x3f, sizeof( dis ) );scanf( "%d", &n );m = n * n * n;for( int i = 1, id;i <= m;i ++ ) {scanf( "%d", &g[i] );do { scanf( "%d", &id ), G[i].push_back( id ); } while( getchar() != '\n' );}int p1, p2, p3;for( int i = 1;i <= m;i ++ ) if( G[i].size() == 3 ) p1 = i;val[1][1][1] = g[p1]; bfs( p1, dis[0] );for( int i = 1;i <= m;i ++ ) if( G[i].size() == 3 and dis[0][i] == (n - 1 << 1) ) p2 = i;val[n][n][1] = g[p2]; bfs( p2, dis[1] );for( int i = 1;i <= m;i ++ ) if( G[i].size() == 3 and dis[0][i] == n - 1 and dis[1][i] == n - 1 ) p3 = i;val[n][1][1] = g[p3]; bfs( p3, dis[2] );for( int i = 1;i <= n;i ++ )for( int j = 1;j <= n;j ++ ) {int d0 = CalcDis( 1, 1, i, j );int d1 = CalcDis( n, n, i, j );int d2 = CalcDis( n, 1, i, j );pos[MAX + d1 - d0][MAX + d2 - d0] = { i, j, 1 };}for( int i = 1;i <= m;i ++ ) {node p = pos[MAX + dis[1][i] - dis[0][i]][MAX + dis[2][i] - dis[0][i]];p.z = dis[0][i] - CalcDis( 1, 1, p.x, p.y ) + 1;val[p.x][p.y][p.z] = g[i];if( ! g[i] ) NB.push_back( p );}dfs( 0 );printf( "%d %d\n", Min, Max );return 0; }

總結

以上是生活随笔為你收集整理的[ZJOI2014] 璀璨光华（bfs建图 + dfs搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。