论坛 › 小题大作 › 关于沙发旋转90度角的问题

mathe 发表于 2019-2-25 09:05:10

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef N
#define N 1
#endif
#define NB (4*N+4)
#define NS (NB*(1<<(N)))
#define STATE_ID(loc, dir)   (((loc)<<(N))|dir)
#define GET_LOC(state)       ((state)>>(N))
#define GET_DIR(state)       ((state)&((1<<(N))-1))
#define GET_DIR_X(state, x)(((state)>>(x))&1)
#define CHANGE_DIR(state, x) ((state)^=(1<<(x)))

long dist;
long count;
intedges;
int get_loc_col(int loc)
{
    if(loc<3)return 0;
    return (loc-3)/2+1;
}

int get_loc_row(int loc)
{
    if(loc<3){
      return loc%3;
    }else{
      return 2*((loc-3)%2);
    }
}

int make_loc(int col, int row)
{
    if(col==0)return row;
    return 3+(col-1)*2+row/2;
}

void build_count(int max_dist)
{
    int i,j;
    for(i=0;i<NS;i++){
      if(dist==1)count=1L;
    }
    for(j=2;j<=max_dist;j++){
      for(i=0;i<NS;i++){
         if(dist==j){
               long cc=0;
               if(edges>=0){
                   if(dist]==j-1){
                     cc+=count];
                   }
                   if(edges>=0){
                     if(dist]==j-1){
                           cc+=count];
                     }
                   }
               }
               count=cc;
         }
      }
    }
}


void dump_state(int state)
{
    int loc = GET_LOC(state);
    int dir = GET_DIR(state);
    int col = get_loc_col(loc);
    int row = get_loc_row(loc);
    int i;int p=0;
    for(i=0;i<2*N+2;i++){
       p=0;
       if(row==0&&col==i){
         printf("%c",'P');p=1;
       }else{
         if(i>0&&i<2*N+1){
               int sofa_id=(i-1)/2;
               if((i&1)==0&&GET_DIR_X(state,sofa_id)==0){
                  printf("%c",'|');p=1;
               }
         }
         if(!p)printf("%c",'O');
       }
    }
    printf("\n");
    for(i=0;i<2*N+2;i++){
       if(i==0||i==2*N+1){
         if(row==1&&col==i){
               printf("%c",'P');
         }else{
               printf("%c",'O');
         }
       }else if((i&1)==1){
         printf("%c",'-');
       }else{
         int sofa_id=(i-1)/2;
         if(GET_DIR_X(state,sofa_id)==0){
               printf("%c",'J');
         }else{
               printf("%c",'7');
         }
       }
    }
    printf("\n");
    for(i=0;i<2*N+1;i++){
       if(row==2&&col==i){
          printf("%c",'P');
       }else{
          int sofa_id=(i-1)/2;
          p=0;
          if(i>0){
             if((i&1)==0&&GET_DIR_X(state,sofa_id)==1){
                printf("%c",'|');p=1;
             }
          }
          if(!p)printf("%c",'O');
       }
    }
    printf("\n");
}

//return num_states, return -1 if any error
int get_next_state(int cur_state, int next_states)
{
    int loc = GET_LOC(cur_state);
    int dir = GET_DIR(cur_state);
    int col = get_loc_col(loc), row=get_loc_row(loc);
    int sofa_id = (col-1)/2;
    int num_states=0;
    if(col==0){
      if(row==0){
         next_states=STATE_ID(make_loc(1,0), dir);
         next_states=STATE_ID(make_loc(0,1), dir);
         num_states=2;
      }else if(row==1){
         next_states=STATE_ID(make_loc(0,0), dir);
         next_states=STATE_ID(make_loc(0,2), dir);
         num_states=2;
      }else if(row==2){
         next_states=STATE_ID(make_loc(0,1), dir);
         next_states=STATE_ID(make_loc(1,2), dir);
         num_states=2;
      }else{
         num_states=-1;//invalid state
      }
    }else if(col==2*N+1){
      if(row==0){
         dist=1;//next is one of exits
      }else{
         num_states=-1;//invalid state
      }
    }else if(col%2==1){
      if(row==0){
            if(sofa_id==0||GET_DIR_X(cur_state,sofa_id-1)==1){
                next_states=STATE_ID(make_loc(col-1,row), dir);
            }
            if(sofa_id>0&&GET_DIR_X(cur_state,sofa_id-1)==0){
                next_states=STATE_ID(make_loc(col-2,row),CHANGE_DIR(dir,sofa_id-1));
            }
            if(GET_DIR_X(cur_state,sofa_id)==0){
                next_states=STATE_ID(make_loc(col,2), CHANGE_DIR(dir,sofa_id));
            }
            if(GET_DIR_X(cur_state,sofa_id)==1){
                next_states=STATE_ID(make_loc(col+1,0), dir);
            }
      }else if(row==2){
            if(sofa_id==0||GET_DIR_X(cur_state,sofa_id-1)==0){
                next_states=STATE_ID(make_loc(col-1,row),dir);
            }
            if(sofa_id>0&&GET_DIR_X(cur_state,sofa_id-1)==1){
                next_states=STATE_ID(make_loc(col-2,row), CHANGE_DIR(dir, sofa_id-1));
            }
            if(GET_DIR_X(cur_state,sofa_id)==1){
                next_states=STATE_ID(make_loc(col,0), CHANGE_DIR(dir,sofa_id));
            }
            if(GET_DIR_X(cur_state,sofa_id)==0){
                next_states=STATE_ID(make_loc(col+1,2),dir);
            }
      }else{
            num_states=-1;
      }
    }else{
      if(row==0){
            if(GET_DIR_X(cur_state,sofa_id)==0){
                num_states=-1;//invalid state
            }else{
                next_states=STATE_ID(make_loc(col-1,0),dir);
                next_states=STATE_ID(make_loc(col+1,0),dir);
            }
      }else if(row==2){
            if(GET_DIR_X(cur_state,sofa_id)==1){
                num_states=-1;//invalid state
            }else{
                next_states=STATE_ID(make_loc(col-1,2),dir);
                if(sofa_id<N-1){
                   next_states=STATE_ID(make_loc(col+1,2),dir);
                }
            }
      }else{
            num_states=-1;
      }
    }
    return num_states;
}

void build_edges()
{
    int i;
    int next_states;
    for(i=0;i<NS;i++){
      int num_edges=get_next_state(i,next_states);
      if(num_edges==0){
             edges=edges=-1; //destine states
            
      }else if(num_edges==-1){
             edges=edges=-2; //invalid states
      }else if(num_edges==1){
             edges=next_states;
             edges=-1;
      }else if(num_edges==2){
             edges=next_states;
             edges=next_states;
      }else{
             fprintf(stderr,"Invalid in building edges\n");
             exit(-1);
      }
    }
}

void dump_edges()
{
    int i,j;
    for(i=0;i<NS;i++){
      for(j=0;j<2;j++){
             if(edges<0)break;
             printf("edge:%x(%ld)=>%x(%ld)\n",i,dist,edges,dist]);
             dump_state(i);
             printf("=>\n");
             dump_state(edges);
      }
    }
}

void dump_dists()
{
    int i;
    for(i=0;i<NS;i++){
       printf("state %x, dist %ld\n",i,dist);
       dump_state(i);
    }
}

void init_dist()
{
    int i;
    for(i=0;i<NS;i++)dist=-1;
}

void build_dist()
{
    int i,j,k;
    for(i=0;i<NS;i++)for(j=0;j<NS;j++){
      for(k=0;k<2;k++){
            int target = edges;
            if(target<0)break;
            if(dist<0)continue;
            if(dist==-1||dist+1<dist)dist=dist+1;
      }
    }
}

void visit(int state)
{
    int i,j;
    long len=dist;
    for(i=(int)len;i>=1;i--){
      dump_state(state);
      printf("(%0x)=>\n",state);
      int next_state=-1;
      for(j=0;j<2;j++){
            if(edges<0)break;
            if(dist]!=i-1)continue;
            next_state=edges; break;
      }
      if(next_state<0&&i>1){
            fprintf(stderr,"Fail to find next state, invalid code\n");
            exit(-1);
      }
      state=next_state;
    }
    printf("Exit\n");
}

int main()
{
    init_dist();
    build_edges();
    build_dist();
    int start_state = STATE_ID(make_loc(0,1),0);
    build_count(dist);
    if(dist>=0){
         printf("Best dist %ld, totoal count %ld\n",dist,count);
         visit(start_state);
    }else{
         printf("Fail to find result\n");
    }
//    dump_edges();
//    dump_dists();
    return 0;
}

道路千万条，最短仅一条；代码无注释，阅者两行累。

wayne 发表于 2019-2-25 09:47:44

阅者两行累，那作者呢，:lol， 作者是沙洲寂寞冷。

风云剑 发表于 2019-2-25 11:25:42

看着头疼，思路是不是BFS？

王守恩 发表于 2019-2-25 18:53:06

本帖最后由 王守恩 于 2019-2-26 06:43 编辑

谢谢mathe！
给出119的行走路线。本人不会画图，只能将就了。
上排共 10 格。
第1格16个数：1,6,14,19,30,35,43,48,62,67,75,80,91,96,104,109,
第2格16个数：2,7,15,20,31,36,44,49,63,68,76,81,92,97,105,110,
第3格8个数：8,21,37,50,69,82,98,111,
第4格8个数：9,22,38,51,70,83,99,112,
第5格4个数：23,52,84,113,
第6格4个数：24,53,85,114,
第7格2个数：54,115,
第8格2个数：55,116,
第9格1个数：117,
第10格1个数:118,
中排共 10 格。
第1格16个数：0,5,13,18,29,34,42,47,61,66,74,79,90,95,103,108,
第2——10格为空格
下排共 10 格。
第1格15个数：4,12,17,28,33,41,46,60,65,73,78,89,94,102,107,
第2格15个数：3,11,16,27,32,40,45,59,64,72,77,88,93,101,106,
第4格7个数：10,26,39,58,71,87,100,
第6格3个数：25,57,86,
第8格1个数：56,
第10格1个数:119.
第3,5,7,9格为空格

补充内容 (2019-2-26 07:57):
请版主删除。

王守恩 发表于 2019-2-26 07:55:27

本帖最后由 王守恩 于 2019-2-26 08:31 编辑

王守恩 发表于 2019-2-25 18:53
谢谢mathe！
给出119的行走路线。本人不会画图，只能将就了。
上排共 10 格。


119 可以这样表示。
第 1 个 “出” 表示 “3”
第 2 个 “出” 表示 “10”
第 3 个 “出” 表示 “25”
第 4 个 “出” 表示 “56”
第 5 个 “出” 表示 “119”
规律：凡是第\(\ 2^n\ \)行就有1个 “出”

原-上-右-出-左
-上-上-右-右-右-出-左-左
-上-上-右-下-左
-上-上-右-右-右-右-右-出-左-左-左
-上-上-右-下-左
-上-上-右-右-右-下-左-左
-上-上-右-下-左
-上-上-右-右-右-右-右-右-右-出-左-左-左-左
-上-上-右-下-左
-上-上-右-右-右-下-左-左
-上-上-右-下-左
-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左
-上-上-右-右-右-下-左-左
-上-上-右-下-左
-上-上-右-右-右-右-右-右-右-右-右-出

王守恩 发表于 2019-2-26 09:08:54

本帖最后由 王守恩 于 2019-2-26 10:21 编辑

王守恩 发表于 2019-2-26 07:55
119 可以这样表示。
第 1 个 “出” 表示 “3”
第 2 个 “出” 表示 “10”


246 可以这样表示。
原-上-右-下-左-上-上-右-右-右-下-左-左
-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左
-上-上-右-下-左-上-上-右-右-右-右-右-右-右-下-左-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左
-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左
-上-上-右-下-左-上-上-右-右-右-右-右-右-右-右-右-下-左-左-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左
-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左
-上-上-右-下-左-上-上-右-右-右-右-右-右-右-下-左-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左
-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左
-上-上-右-下-左-上-上-右-右-右-右-右-右-右-右-右-右-右-出

王守恩 发表于 2019-2-26 10:46:42

王守恩 发表于 2019-2-26 09:08
246 可以这样表示。
原-上-右-下-左-上-上-右-右-右-下-左-左
-上-上-右-下-左-上-上-右-右-右-右- ...

501 可以这样表示。
原-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-右-右-下-左-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-右-右-右-右-下-左-左-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-右-右-下-左-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-右-右-右-右-右-右-下-左-左-左-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-右-右-下-左-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-右-右-右-右-下-左-左-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-右-右-下-左-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-下-左-左-左
-上-上-右-下-左-上-上-右-右-右-下-左-左-上-上-右-下-左-上-上-右-右-右-右-右-右-右-右-右-右-右-右-右-出

mathe 发表于 2019-2-26 17:58:07

假设n张沙发走的路径为$S_n$-出。那么对于n+1张沙发的情况，走 "$S_n$-下-n个左-上-$S_n$-右-右-出" 即可
由于S_n的长度为a_n-1,所以可以计算得$a_{n+1}=2a_n+n+3$

王守恩 发表于 2019-2-27 09:03:21

本帖最后由 王守恩 于 2019-2-27 09:05 编辑

mathe 发表于 2019-2-26 17:58
假设n张沙发走的路径为$S_n$-出。那么对于n+1张沙发的情况，走 "$S_n$-下-n个左-上-$S_n$-右-右-出" 即可
...

         用二进制来表示A000247
3, 10, 25, 56, 119, 246, 501, 1012, 2035, 4082, 8177, 16368, 32751, 65518, 131053,
262124, 524267, 1048554, 2097129, 4194280, 8388583, 16777190, 33554405, 67108836,
134217699, 268435426, 536870881, 1073741792, 2147483615,
                                                               
                                                             1 1=               
                                                         1 0 1 0=1+2
                                                       1 1 0 0 1=2+1
                                                   1 1 1 0 0 0=3+0=2+8
                                                   1 1 1 0 1 1 1=3+7
                                                 1 1 1 1 0 1 1 0=4+6
                                             1 1 1 1 1 0 1 0 1=5+5
                                             1 1 1 1 1 1 0 1 0 0=6+4
                                           1 1 1 1 1 1 1 0 0 1 1=7+3
                                       1 1 1 1 1 1 1 1 0 0 1 0=8+2
                                       1 1 1 1 1 1 1 1 1 0 0 0 1=9+1
                                     1 1 1 1 1 1 1 1 1 1 0 0 0 0=10+0=9+16
                                 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1=10+15
                                 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0=11+14
                               1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1=12+13
                           1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0=13+12
                           1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1=14+11
                         1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0=15+10
                     1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1=16+9
                     1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0=17+8
                   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1=18+7
               1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0=19+6
               1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1=20+5
             1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0=21+4
         1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1=22+3
         1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0=23+2
       1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1=24+1
   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0=25+0=24+32
   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1=25+31
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0=26+30
         
                  
         

dlpg070 发表于 2019-2-27 13:12:02

王守恩 发表于 2019-2-27 09:03
用二进制来表示A000247
3, 10, 25, 56, 119, 246, 501, 1012, 2035, 4082, 8177, 16368, ...

通项公式 ：a (n) = 2^n - n - 2.n >= 4
{10, 25, 56, 119, 246, 501, 1012, 2035, 4082, 8177, 16368, 32751, \
65518, 131053, 262124, 524267, 1048554}

查看完整版本: 关于沙发旋转90度角的问题