Cube-3

From

Oleg Khovayko ()

To

Oleg Khovayko

Date

2002-11-05T14:29:26Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

Написал я предыдущую версию про кубик, все вроде как
работает, опубликовал - а потом подумал: Понятно, что
где-то к доске кубик не имеет права приклеиваться, ибо дальше не
сможет катиться. А касается ли это ограничение последней
точки (точки назначения)?!?!?!??
Я так поразмыслил, что нет - ибо надо, чтобы кубик просто
здесь оказался. А уж в приклееном состоянии или нет - неважно.
Поэтому пришлось модифицировать алгоритм, чтобы он точку
назначения корректно обрабатывал - то есть чтобы можно было ее
тоже клеем смазывать и/или кубик мог на нее падать клейкой
стороной. Ниже - третья модификация, которая корректно обслуживает
точку назначения:




#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define M 100
#define N 200

int glued_Y[] = { 0, 2, 1, M-1, -1 };
int glued_X[] = { 1, 1, 2, N-1, -1 };

/*----------------------------------------------------*/

char SQ[M][N];

char Cube_Step[4][6] = {
   { 2, 1, 5, 3, 0, 4 },
   { 3, 0, 2, 5, 4, 1 },
   { 4, 1, 0, 3, 5, 2 },
   { 1, 5, 2, 0, 4, 3 }
};

char X_Step[] = {  0, 1, 0, -1 };
char Y_Step[] = {  1, 0, -1, 0 };

/*----------------------------------------------------*/

void step(int y, int x, const char in_cube) {
   int dir;
   char mask = 1 << in_cube, sq;

   if((x|y) < 0 || y >= M || x >= N)
     return;

   sq = SQ[y][x]; SQ[y][x] |= mask | 0200;

   if(SQ[M-1][N-1] >= 0 && in_cube != 5 && (sq & mask) == 0)
     for(dir = 0; dir < 4; dir++)
       step(y + Y_Step[dir], x + X_Step[dir], Cube_Step[dir][in_cube]);
} /* step */

/*----------------------------------------------------*/

void main() {
	int i;
     memset(&SQ, 0, M * N);

     for(i = 0; glued_X[i] >= 0; i++)
       SQ[glued_Y[i]][glued_X[i]] = 0177;

     step(0, 0, 0);

     puts(SQ[M-1][N-1] < 0? "Found way\n" : "No ways\n");
}

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)