|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Khovayko 2:5020/400 05 Nov 2002 15:29:26
To : Oleg Khovayko
Subject : Cube-3
--------------------------------------------------------------------------------
Hаписал я предыдущую версию про кубик, все вроде как
работает, опубликовал - а потом подумал: Понятно, что
где-то к доске кубик не имеет права приклеиваться, ибо дальше не
сможет катиться. А касается ли это ограничение последней
точки (точки назначения)?!?!?!??
Я так поразмыслил, что нет - ибо надо, чтобы кубик просто
здесь оказался. А уж в приклееном состоянии или нет - неважно.
Поэтому пришлось модифицировать алгоритм, чтобы он точку
назначения корректно обрабатывал - то есть чтобы можно было ее
тоже клеем смазывать и/или кубик мог на нее падать клейкой
стороной. Hиже - третья модификация, которая корректно обслуживает
точку назначения:
#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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
