/* * @(#) msu97_d.c - Problem 'D' ("The cubical races") solution * of the ACM Programming Contest at the MSU in 1997. * (c) 1998 Ivan Maidanski http://ivmai.chat.ru * Freeware program source. All rights reserved. ** * Language: ANSI C * Tested with: Borland C++ v3.1 * Last modified: 1998-04-03 17:00:00 GMT+04:00 */ /* Input data file: d.dat */ #include /* CHAR_BIT */ #include /* FILE, fopen(), fscanf(), printf() */ #define MAXN 100 #define MAXSPEED 3 int ntests,w,h,xd,yd; char map[MAXN][(MAXN+CHAR_BIT-1)/CHAR_BIT]; char trace[MAXN][(MAXN+CHAR_BIT-1)/CHAR_BIT][MAXSPEED*2+1][MAXSPEED*2+1]; char newtrace[MAXN][(MAXN+CHAR_BIT-1)/CHAR_BIT][MAXSPEED*2+1][MAXSPEED*2+1]; int check_finish(void) { int vx,vy; for (vy=-MAXSPEED;vy<=MAXSPEED;vy++) for (vx=-MAXSPEED;vx<=MAXSPEED;vx++) if ((trace[yd][xd/CHAR_BIT][vy+MAXSPEED][vx+MAXSPEED]>>(xd%CHAR_BIT))&1) return 1; return 0; } int check_reached(int i, int j, int vy, int vx, int ay, int ax) { if ((i-=vy)<0 || i>=h || (j-=vx)<0 || j>=w || (vy-=ay)<-MAXSPEED || vy>MAXSPEED || (vx-=ax)<-MAXSPEED || vx>MAXSPEED) return 0; return (trace[i][j/CHAR_BIT][vy+MAXSPEED][vx+MAXSPEED]>>(j%CHAR_BIT))&1; } int main(void) { int i,j,vx,vy,step,flag; char c; FILE *f=fopen("d.dat","rt"); fscanf(f,"%*[^0-9]%d",&ntests); while (ntests--) { fscanf(f,"%*[^0-9]%d%*[^0-9]%d%*[^0-9]%d%*[^0-9]%d",&w,&h,&xd,&yd); for (i=h-1;i>=0;i--) for (j=0;j>(j%CHAR_BIT))&1) for (vy=-MAXSPEED;vy<=MAXSPEED;vy++) for (vx=-MAXSPEED;vx<=MAXSPEED;vx++) if (!((trace[i][j/CHAR_BIT][vy+MAXSPEED][vx+MAXSPEED]>> (j%CHAR_BIT))&1) && (check_reached(i,j,vy,vx,0,0) || check_reached(i,j,vy,vx,0,-1) || check_reached(i,j,vy,vx,0,1) || check_reached(i,j,vy,vx,-1,0) || check_reached(i,j,vy,vx,1,0))) newtrace[i][j/CHAR_BIT][vy+MAXSPEED][vx+MAXSPEED]|= (flag=1)<<(j%CHAR_BIT); for (i=0;i>(j%CHAR_BIT))&1) for (vy=-MAXSPEED;vy<=MAXSPEED;vy++) for (vx=-MAXSPEED;vx<=MAXSPEED;vx++) if (!((trace[i][j/CHAR_BIT][vy+MAXSPEED][vx+MAXSPEED]>> (j%CHAR_BIT))&1) && ((newtrace[i][j/CHAR_BIT][vy+MAXSPEED][vx+MAXSPEED]>> (j%CHAR_BIT))&1)) trace[i][j/CHAR_BIT][vy+MAXSPEED][vx+MAXSPEED]|=1<<(j%CHAR_BIT); } printf("-----\n" "The destination point "); if (flag) printf("has reached in %d turns.\n",step); else printf("cannot be reached.\n"); } printf("\n"); return 0; }