HDU 3871 Cubic Maze 【Simulation Building Graph + BFS】【废题,不要看了,不知道现在数据改成什么鬼德性了。。这份代码和标程都交不过去了。】

Cubic Maze

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/32768 K (Java/Others)
Total Submission(s): 14    Accepted Submission(s): 7


Problem Description
Consider an N*N*N cubic maze. We create the coordinate system as the picture below.
Now a robot is in the maze. It can be represented as a vector from his foot to head, and we call this vector the roboctor. To discribe the direction the robot will move to, we use a direct vector, which is prependicular to the roboctor. Both the roboctor and the direct vector must parallel to the coordinate axes. The robot can only be in the integral point. The robot can't go beyond the bound of the maze(i.e. The (1,1,1)->(N,N,N) space).

The robot can execute the following 6 instructions:

  • F instruction. Move 1 unit along the direct vector.

  • L instruction. Turn the direct vector left 90 degree around the roboctor with the roboctor unchanged.

  • R instruction. Turn the direct vector right 90 degree around the roboctor with the roboctor unchanged.

  • U instruction. Change the direct vector to the original roboctor and change the roboctor to the opposite of the original direct vector.

  • D instruction. Change the direct vector to the opposite of the original roboctor and change the roboctor to the original direct vector.

  • B instruction. Change the direct vector to the opposite of the original direct vector.


The instructions are NUMBERED FROM 1 TO 6 AS ABOVE. 

There are some bombs in some integral points in the maze. The robot must avoid to move to the bomb point. For each integral point, we use 1 to represent the bomb and 0 for not. We have the map of the maze, but it is encoded. The map is encoded as follows:

Encode the N integral points with the same X coordinate and the same Z coordinate along the negative Y direction as a 0/1 string, and convert it to a 8-based number. The 8-based number is the code we get.

The entire maze can be represented by N*N 8-based numbers.

At first, the robot is at an integral point A(xa,ya,za), with direct vector DA and roboctor RA. The destination condition of the robot is to be on an integral point B(xb,yb,zb) with the direct vector DB and the roboctor RB. Your mission is to give a series of instructions to guide the robot to get to the destination condition safely(i.e. Not to hit any single bomb) with the least number of instructions. 

DA, RA, DB, RB will be represented as 1~6. 1~3 represents the positive direction of X, Y, Z axis respectively. 4~6 represents the negative direction of X, Y, Z axis respectively.
 

Input
An integer T comes first indicating the number of test cases. Each case contains N+3 lines:
The first line contains an integer number N (3<=N<=30) representing the cubic space.
The second line contains 5 space separated integer numbers xa,ya,za,DA,RA (1<=xa, ya, za<=N,1<=DA, RA<=6) representing the start condition.
The third line contains 5 space separated integer numbers xb,yb,zb,DB,RB (1<=xb, yb, zb<=N, 1<=DB, RB<=6) representing the destination condition.
The following N lines each contains N 8-based space separated numbers, representing the maze. The jth number of the ith line represents a line whose X coordinate is j and Z coordinate is i in the maze.

There may exist a bomb even in the start or the destination.
 

Output
For each case, print one or two lines. If the robot can't get to the destination condition, print a line “Sorry, I can't get there.” (without quotes). If the robot can get to the destination condition, print two lines. The first line contains one integer indicating the least number of instructions. The second line is the instruction sequence without spaces. If there exists more than one such instruction, print the 
one with the least instruction number.
 

Sample Input
2
5
1 1 1 6 4
5 5 5 6 4
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
3
1 1 1 6 5
3 3 3 4 6
6 0 0
0 0 4
0 6 2
 

Sample Output
17
RFFFFRFFFFUBFFFFU
Sorry, I can't get there.
 

Source


这tmd哪里是搜索啊。。俨然就是考察人肉建图能力的。。。
状态转移为5维,x,y,z,rot,dir。。。
6种操作对应6个状态转移数组,前进:2维,左右转:对称的2维,上下转:1维,后转:1维。
8进制->2进制转化建图。
BFS硬搞,PFS反而因为搜索顺序的问题不好写。所以就写了个裸的BFS。
回溯求解,两个5维数组的状态转移回溯。
sb杭电内存给小了,各种MLE。改了一堆short和char还有数组大小什么的才过。。。

详见代码:
#include <iostream>
#include 
<cstdio>
#include 
<queue>
#include 
<cstring>
using namespace std;
#define maxn 31
bool mat[maxn][maxn][maxn];
struct point
{
    
short x,y,z,rot,dir,step;
    point(){}
    point(
int a,int b,int c,int d,int e):x(a),y(b),z(c),rot(d),dir(e){}
    
bool operator ==(const point q)
    {
        
return x == q.x && y == q.y && z == q.z && rot == q.rot && dir == q.dir;
    }
}ST,EN;
int n;
char opt[10= {0,'F','L','R','U','D','B'};
point pre[maxn][maxn][maxn][
7][7];
short step[maxn][maxn][maxn][7][7];
int dis[maxn][maxn][maxn][7][7];
int LEFT[7][7= 
{
    
0,0,0,0,0,0,0,
    
0,0,3,5,0,6,2,
    
0,6,0,1,3,0,4,
    
0,2,4,0,5,1,0,
    
0,0,6,2,0,3,5,
    
0,3,0,4,6,0,1,
    
0,5,1,0,2,4,0
};
int RIGHT[7][7= 
{
    
0,0,0,0,0,0,0,
    
0,0,6,2,0,3,5,
    
0,3,0,4,6,0,1,
    
0,5,1,0,2,4,0,
    
0,0,3,5,0,6,2,
    
0,6,0,1,3,0,4,
    
0,2,4,0,5,1,0
};
int dx[7= {0,1,0,0,-1,0,0};
int dy[7= {0,0,1,0,0,-1,0};
int dz[7= {0,0,0,1,0,0,-1};
int back[7= { 0,4,5,6,1,2,3 };
char record[maxn * maxn * maxn * 10 * 10];
bool check(point p)
{
    
int x = p.x,y = p.y,z = p.z;
    
return (1 <= x && x <= n) && (1 <= y && y <= n) && (1 <= z && z <= n) && !mat[x][y][z];
}
queue 
<point> Q;
void bfs()
{
    
while(!Q.empty())
        Q.pop();
    
int x = ST.x,y = ST.y,z = ST.z,rot = ST.rot,dir = ST.dir;
    
if(!check(ST))
        
return ;
    dis[x][y][z][rot][dir] 
= 0;
    
if(ST == EN)
        
return ;
    pre[x][y][z][rot][dir] 
= ST;
    ST.step 
= 0;
    Q.push(ST);
    
while(!Q.empty())
    {
        point now 
= Q.front();
        Q.pop();
        
for(int i = 1;i <= 6;i++)
        {
            
if(i == 1)
            {
                rot 
= now.rot;
                dir 
= now.dir;
                x 
= now.x + dx[now.dir];
                y 
= now.y + dy[now.dir];
                z 
= now.z + dz[now.dir];
            }
            
else
            {
                
if(i == 2)
                {
                    rot 
= now.rot;
                    dir 
= LEFT[now.rot][now.dir];
                }
                
else if(i == 3)
                {
                    rot 
= now.rot;
                    dir 
= RIGHT[now.rot][now.dir];
                }
                
else if(i == 4)
                {
                    rot 
= back[now.dir];
                    dir 
= now.rot;
                }
                
else if(i == 5)
                {
                    rot 
= now.dir;
                    dir 
= back[now.rot];
                }
                
else
                {
                    rot 
= now.rot;
                    dir 
= back[now.dir];
                }
                x 
= now.x;
                y 
= now.y;
                z 
= now.z;
            }
            
            
if(check(point(x,y,z,rot,dir)) && dis[x][y][z][rot][dir] > now.step + 1)
            {
                dis[x][y][z][rot][dir] 
= now.step + 1;
                pre[x][y][z][rot][dir] 
= now;
                step[x][y][z][rot][dir] 
= i;
                point haha(x,y,z,rot,dir);
                haha.step 
= now.step + 1;
                Q.push(haha);
            }
        }
    }
}
void come(int temp)
{
    record[temp 
+ 1= 0;
    point rc 
= EN;
    
while(!(rc == ST))
    {
        
int x = rc.x,y = rc.y,z = rc.z,rot = rc.rot,dir = rc.dir;
        record[temp
--= opt[step[x][y][z][rot][dir]];
        rc 
= pre[x][y][z][rot][dir];
    }
}
void solve()
{
    scanf(
"%d",&n);
    
int a,b,c,d,e;
    memset(mat,
0,sizeof(mat));
    
for(int i = 0;i < 2;i++)
    {
        scanf(
"%d %d %d %d %d",&a,&b,&c,&d,&e);
        
if(i == 0)
            ST 
= point(a,b,c,e,d);
        
else
            EN 
= point(a,b,c,e,d);
    }
    
for(int i = 1;i <= n;i++)
    {
        
for(int j = 1;j <= n;j++)
        {
            
char str[15];
            str[
0= 'x';
            scanf(
" %s",&str[1]);
            
int l = strlen(str);
            
bool code[35];
            memset(code,
0,sizeof(code));
            
for(int q = l - 1;q >= 1;q--)
            {
                
int fuck = str[q] - '0';
                
for(int k = 1;k <= 3;k++)
                {
                    
if(fuck & 1)
                        code[(l 
- q - 1* 3 + k] = 1;
                    fuck 
>>= 1;
                }
            }
            
for(int k = n;k >= 1;k --)
                mat[j][k][i] 
= code[k];
        }
    }
    memset(dis,
0x7f,sizeof(dis));
    memset(pre,
0,sizeof(pre));
    memset(step,
0,sizeof(step));
    bfs();
    
if(dis[EN.x][EN.y][EN.z][EN.rot][EN.dir] == 0x7f7f7f7f)
        puts(
"Sorry, I can't get there.");
    
else
    {
        
int ans = dis[EN.x][EN.y][EN.z][EN.rot][EN.dir];
        come(ans);
        printf(
"%d\n",ans);
        puts(
&record[1]);
    }
}
int main()
{
    
int t;
    scanf(
"%d",&t);
    
for(int i = 0;i < t;i++)solve();
}

posted on 2011-07-23 15:57 BUPT-[aswmtjdsj] @ Penalty 阅读(348) 评论(0)  编辑 收藏 引用 所属分类: HDU Solution Report 模拟搜索


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年7月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜