POJ 3322 Bloxorz I-白红宇

POJ 3322 Bloxorz I

阅读量：6499 次

发布时间：2019-06-24

本文共 7592 字，大约阅读时间需要 25 分钟。

首先呢这个题目的名字好啊 ORZ啊

如果看不懂题意的话请戳这里玩儿几盘就懂了【微笑】

就是这个神奇的木块可以各种滚

但是有墙的地方是不能去的有的地方只能躺着走立着会掉下去。（姑且把这种底面叫“软底面”吧）（很坑的）

思路：

搜索（BFS）

一开始是想传5个参数（其实没必要。。。）

① flag flag表示在第几种状态② x1 ③ y1 ④ x2 ⑤ y2（坐标们）

1. flag=0

代表这个木块是立着的这个时候只有x1,y1有用

2. flag=1

代表木块的位置如下图（呃你愿意叫它竖着躺着也好）

这个时候y1,y2相同 x1,x2相差1

3. flag=2

代表木块的位置如下图（呃你愿意叫它横着躺着也好）

这个时候x1,x2相同 y1,y2相差1

每次搜索的时候判一下符不符合

① 不轧墙

② 没有在“软地面”上立着

省略无数次脑残错误。。。

终于AC 了

以下是我的第一个AC代码

//By: Sirius_Ren#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;char a[705][705];char xxs[4][3]={
    {
    1,2,1},{
    0,0,2},{
    0,0,2},{-2,-1,1}},yys[4][2]={
    {
    0,0},{
    1,2},{-2,-1},{
    0,0}};char xx1[4][3]={
    {-1,0,0},{
    2,0,0},{
    0,1,1},{
    0,1,1}},yy1[4][2]={
    {
    0,0},{
    0,0},{
    1,1},{-1,-1}};char xx2[4][3]={
    {-1,-1,2},{
    1,1,2},{
    0,0,0},{
    0,0,0}},yy2[4][2]={
    {
    0,1},{
    0,1},{-1,0},{
    2,0}};int vis[705][705][3];int n,m,ex,ey;struct node{    short flag;    int x1,y1,x2,y2;}J,U;queue
          
            q;int main(){ while(scanf("%d%d",&n,&m)&&(n||m)) { J.flag=1;J.x1=J.x2=J.y1=J.y2=0; memset(vis,-1,sizeof(vis)); for(int i=1;i<=n;i++) for(int j=01;j<=m;j++) { cin>>a[i][j]; if(a[i][j]=='X') { if(J.flag) J.x1=i,J.y1=j,J.flag=!J.flag; else J.x2=i,J.y2=j,J.flag=!J.flag; } else if(a[i][j]=='O')ex=i,ey=j; }// printf("%d %d",ex,ey); if(J.x1==J.x2)J.flag=2; vis[J.x1][J.y1][J.flag]=0; q.push(J); while(!q.empty()) { J=q.front();q.pop();// printf("J=%d flag=%d x1=%d y1=%d x2=%d y2=%d\n",vis[J.x1][J.y1][J.flag],J.flag,J.x1,J.y1,J.x2,J.y2); if(J.x1==ex&&J.y1==ey&&!J.flag)break; if(!J.flag) { for(int i=0;i<4;i++) { int F=0; for(int j=0;j<=1;j++) { if(a[J.x1+xxs[i][j]][J.y1+yys[i][j]]=='#')F=1; } U.flag=xxs[i][2],U.x1=J.x1+xxs[i][0],U.x2=J.x1+xxs[i][1],U.y1=J.y1+yys[i][0],U.y2=J.y1+yys[i][1]; if(F||~vis[U.x1][U.y1][U.flag])continue; vis[U.x1][U.y1][U.flag]=vis[J.x1][J.y1][J.flag]+1; // printf("U=%d %d %d %d %d %d\n",i,U.flag,U.x1,U.y1,U.x2,U.y2); q.push(U); } } else if(J.flag==1) { for(int i=0;i<4;i++) { int F=0; for(int j=0;j<=1;j++) { if(a[J.x1+xx1[i][j]][J.y1+yy1[i][j]]=='#')F=1; } U.flag=xx1[i][2],U.x1=J.x1+xx1[i][0],U.x2=J.x1+xx1[i][1],U.y1=J.y1+yy1[i][0],U.y2=J.y1+yy1[i][1]; if(F||~vis[U.x1][U.y1][U.flag]||(!U.flag&&a[U.x1][U.y1]=='E'))continue; vis[U.x1][U.y1][U.flag]=vis[J.x1][J.y1][J.flag]+1; // printf("U=%d %d %d %d %d %d\n",i,U.flag,U.x1,U.y1,U.x2,U.y2); q.push(U); } } else if(J.flag==2) { for(int i=0;i<4;i++) { int F=0; for(int j=0;j<=1;j++) { if(a[J.x1+xx2[i][j]][J.y1+yy2[i][j]]=='#')F=1; } U.flag=xx2[i][2],U.x1=J.x1+xx2[i][0],U.x2=J.x1+xx2[i][1],U.y1=J.y1+yy2[i][0],U.y2=J.y1+yy2[i][1]; if(F||~vis[U.x1][U.y1][U.flag]||(!U.flag&&a[U.x1][U.y1]=='E'))continue; vis[U.x1][U.y1][U.flag]=vis[J.x1][J.y1][J.flag]+1; // printf("U=%d %d %d %d %d %d\n",i,U.flag,U.x1,U.y1,U.x2,U.y2); // printf("%d %d \n",vis[U.x1][U.y1][U.flag],vis[J.x1][J.y1][J.flag]); q.push(U); } } } if(~vis[ex][ey][0])printf("%d\n",vis[ex][ey][0]); else printf("Impossible\n"); while(!q.empty())q.pop(); }}/*7 7########..X####..X#O##....E##....E##.....########8 17########################.......####....##...##..####.........##....##.X..#######..O.##....#######....##############...##################7 7########..X####..##O##....E##....E##.....########0 0*/

这时候我发现了一个问题: 如果每回指定flag为一个值的时候木块的方向，就可以在结构体里面只传3个参数了，随后我就试了试。

的确是这样

//By: Sirius_Ren#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;char a[705][705];char xxs[4][3]={
    {
    1,2,1},{
    0,0,2},{
    0,0,2},{-2,-1,1}},yys[4][2]={
    {
    0,0},{
    1,2},{-2,-1},{
    0,0}};char xx1[4][3]={
    {-1,0,0},{
    2,0,0},{
    0,1,1},{
    0,1,1}},yy1[4][2]={
    {
    0,0},{
    0,0},{
    1,1},{-1,-1}};char xx2[4][3]={
    {-1,-1,2},{
    1,1,2},{
    0,0,0},{
    0,0,0}},yy2[4][2]={
    {
    0,1},{
    0,1},{-1,0},{
    2,0}};int vis[705][705][3];int n,m,ex,ey,x2,y2;struct node{    short flag;    int x1,y1;}J,U;queue
          
            q;int main(){ while(scanf("%d%d",&n,&m)&&(n||m)) { J.flag=1;J.x1=J.y1=x2=y2=0; memset(vis,-1,sizeof(vis)); for(int i=1;i<=n;i++) for(int j=01;j<=m;j++) { cin>>a[i][j]; if(a[i][j]=='X') { if(J.flag) J.x1=i,J.y1=j,J.flag=!J.flag; else x2=i,y2=j,J.flag=!J.flag; } else if(a[i][j]=='O')ex=i,ey=j; } if(J.x1==x2)J.flag=2; vis[J.x1][J.y1][J.flag]=0; q.push(J); while(!q.empty()) { J=q.front();q.pop(); if(J.x1==ex&&J.y1==ey&&!J.flag)break; if(!J.flag) { for(int i=0;i<4;i++) { int F=0; for(int j=0;j<=1;j++) { if(a[J.x1+xxs[i][j]][J.y1+yys[i][j]]=='#')F=1; } U.flag=xxs[i][2],U.x1=J.x1+xxs[i][0],U.y1=J.y1+yys[i][0]; if(F||~vis[U.x1][U.y1][U.flag])continue; vis[U.x1][U.y1][U.flag]=vis[J.x1][J.y1][J.flag]+1; q.push(U); } } else if(J.flag==1) { for(int i=0;i<4;i++) { int F=0; for(int j=0;j<=1;j++) { if(a[J.x1+xx1[i][j]][J.y1+yy1[i][j]]=='#')F=1; } U.flag=xx1[i][2],U.x1=J.x1+xx1[i][0],U.y1=J.y1+yy1[i][0]; if(F||~vis[U.x1][U.y1][U.flag]||(!U.flag&&a[U.x1][U.y1]=='E'))continue; vis[U.x1][U.y1][U.flag]=vis[J.x1][J.y1][J.flag]+1; q.push(U); } } else if(J.flag==2) { for(int i=0;i<4;i++) { int F=0; for(int j=0;j<=1;j++) { if(a[J.x1+xx2[i][j]][J.y1+yy2[i][j]]=='#')F=1; } U.flag=xx2[i][2],U.x1=J.x1+xx2[i][0],U.y1=J.y1+yy2[i][0]; if(F||~vis[U.x1][U.y1][U.flag]||(!U.flag&&a[U.x1][U.y1]=='E'))continue; vis[U.x1][U.y1][U.flag]=vis[J.x1][J.y1][J.flag]+1; q.push(U); } } } if(~vis[ex][ey][0])printf("%d\n",vis[ex][ey][0]); else printf("Impossible\n"); while(!q.empty())q.pop(); }}

继续发掘缩短代码的潜能。。。。

我们发现：无论flag等于多少，之后所进行的操作有一定的相似性。我们就可以把它写成一个函数，每次只需把要进行操作的数组传进去就OK了。

//By: Sirius_Ren#include 
     
      #include 
      
       #include 
       
        using namespace std;char xxs[4][3]={
    {1,2,1},{0,0,2},{0,0,2},{-2,-1,1}},yys[4][2]={
    {0,0},{1,2},{-2,-1},{0,0}},a[705][705];char xx1[4][3]={
    {-1,0,0},{2,0,0},{0,1,1},{0,1,1}},yy1[4][2]={
    {0,0},{0,0},{1,1},{-1,-1}};char xx2[4][3]={
    {-1,-1,2},{1,1,2},{0,0,0},{0,0,0}},yy2[4][2]={
    {0,1},{0,1},{-1,0},{2,0}};int vis[705][705][3];int n,m,ex,ey,x2,y2;struct node{short flag;int x1,y1;}J,U;queue
        
          q;inline void f(char xxx[4][3],char yyy[4][2]){    for(int i=0;i<4;i++){
             int F=0;        for(int j=0;j<=1;j++)if(a[J.x1+xxx[i][j]][J.y1+yyy[i][j]]=='#')F=1;        U.flag=xxx[i][2],U.x1=J.x1+xxx[i][0],U.y1=J.y1+yyy[i][0];        if(F||~vis[U.x1][U.y1][U.flag]||(!U.flag&&a[U.x1][U.y1]=='E'))continue;        vis[U.x1][U.y1][U.flag]=vis[J.x1][J.y1][J.flag]+1;        q.push(U);    }}int main(){    while(scanf("%d%d",&n,&m)&&(n||m)){
             J.flag=1;J.x1=J.y1=x2=y2=0;        memset(vis,-1,sizeof(vis));        for(int i=1;i<=n;i++)            for(int j=0;j<=m;j++){
                     scanf("%c",&a[i][j]);                if(a[i][j]=='X')                    if(J.flag) J.x1=i,J.y1=j,J.flag=!J.flag;                    else x2=i,y2=j,J.flag=!J.flag;                else if(a[i][j]=='O')ex=i,ey=j;            }        if(J.x1==x2)J.flag=2;        vis[J.x1][J.y1][J.flag]=0;        q.push(J);        while(!q.empty()){
                 J=q.front();q.pop();            if(J.x1==ex&&J.y1==ey&&!J.flag)break;            if(!J.flag) f(xxs,yys);            else if(J.flag==1) f(xx1,yy1);            else f(xx2,yy2);        }        if(~vis[ex][ey][0])printf("%d\n",vis[ex][ey][0]);        else printf("Impossible\n");        while(!q.empty())q.pop();    }}

这里写图片描述

缩完代码就是爽啊

但是程序好慢。。

找了一下原因

这里写图片描述

All in all,STL不是万能的。它会影响到程序的运行速度。

转载于:https://www.cnblogs.com/SiriusRen/p/6532449.html

你可能感兴趣的文章