up.c
#include <stdio.h> #include <stdlib.h> #define DIM 2 // square lattice #define NDIR (2*DIM) int L; // grid size int nsite; // = (L+1)^2 int *f_visited; // 0/1 = un/occupied int *nnp; // neighbour index int drvec[NDIR][DIM] = { {-1,0}, {0,-1}, {1,0}, {0,1} }; #define DIR_L 0 #define DIR_U 1 #define DIR_R 2 #define DIR_D 3 #define xy2idx(x, y) ((x)+(L+1)*(y)) void idx2xy(int idx, int *x, int *y) { *x = idx % (L+1); *y = idx / (L+1); } void init_misc(int L0) { L=L0; nsite = (L+1)*(L+1); f_visited = (int *)malloc(sizeof(int)*nsite); nnp = (int *)malloc(sizeof(int)*nsite*NDIR); int i,dir; for(i=0;i<nsite;i++) { f_visited[i]=0; int x,y; idx2xy(i, &x, &y); for(dir=0;dir<NDIR;dir++) { int xx= x+drvec[dir][0]; int yy= y+drvec[dir][1]; if(xx<0 || xx>L || yy<0 || yy>L) nnp[i*NDIR+dir] = -1; else nnp[i*NDIR+dir] = xy2idx(xx,yy); #ifdef DEBUG printf("# site %d,%d dir %d pos %d %d nnp=%d\n",x,y,dir,xx,yy,nnp[i*NDIR+dir] ); #endif }//dir }//i } int npath=0; int pos_start, pos_goal; // recursive routine for one step move void proceed(int pos0, int dir_p) { int dir; int dir_ban2=-1; int x,y; idx2xy(pos0, &x,&y); if(dir_p!=-1) dir_ban2 = (dir_p+2)&3; if(pos0 == pos_goal) { #ifdef DEBUG printf("# Goal!\n"); #endif int i; npath++; return; } f_visited[pos0]=1; #ifdef DEBUG printf("Now %d,%d \n", x,y); #endif #ifdef HIT_WALL_MOD int ban_dir = -1; if(x==0) ban_dir = DIR_U; if(x==L) ban_dir = DIR_U; if(y==0) ban_dir = DIR_L; if(y==L) ban_dir = DIR_L; #endif for(dir=0;dir<NDIR;dir++) { if(dir==dir_ban2)continue; #ifdef HIT_WALL_MOD if(dir==ban_dir)continue; #endif int newpos= nnp[pos0*NDIR+dir]; #ifdef DEBUG int xx,yy; if(newpos==-1)printf("# dir %d Newpos out of bound\n",dir); else { idx2xy(newpos, &xx,&yy); printf("# dir %d New %d,%d F=%d\n", dir,xx,yy,f_visited[newpos]); } #endif if(newpos==-1)continue; if(f_visited[newpos]==1) { continue; } else { proceed(newpos, dir); } } f_visited[pos0]=0; } int main(int argc, char **argv) { int ll=atoi(argv[1]); init_misc(ll); pos_goal = xy2idx(L,L); #ifdef HIT_WALL_MOD f_visited[xy2idx(0,0)]=1; pos_start= xy2idx(1,0); proceed(pos_start, 2); #else pos_start= xy2idx(0,0); proceed(pos_start, -1); #endif #ifdef HIT_WALL_MOD npath *= 2; #endif printf("L=%d N=%d\n",L, npath); }