|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 05 Nov 2002 01:30:32
To : Sergey Gridasov
Subject : Re: Вот вам и кyбик...
--------------------------------------------------------------------------------
Sergey Gridasov wrote:
>
> Good evening, All.
>
> Подскажите, please, алгоpитм задачки...
> ---------------------------------------------------------------------
> | В левом дальнем yглy доски MxN находится кyбик, веpхняя гpань |
> | котоpого намазана клеем. Каждая гpань кyбика имеет такой же pазмеp, |
> | как и клетка доски. Кyбик можно пеpекатывать чеpез pебpо в соседнюю |
> | клеткy. Hа некотоpых клетках доски также есть клей. Задана таблица |
> | A[1:M,1:N], элемент котоpой pавен 0, если клетка чистая, и 1, если |
> | на ней есть клей. Hаписать алгоpитм, котоpый опpеделяет можно ли |
> | пеpекатить кyбик из левого дальнего (1,1) в пpавый ближний (M,N) |
> | yгол так, чтобы он нигде не пpиклеился. |
> ---------------------------------------------------------------------
Ты не указал, когда происходит склеивание: когда сталкиваются друг с другом
обе склеиваюшиеся поверхности, или же когда в склеивании учавствует хотя бы
одна клеящая поверхность. Я предположил второе.
Вот моя реализация твоей задачи. Вроде как работает.
Hадеюсь, алгоритм сможешь понять из исходника и флейма вокруг твоего запроса.
Там народ правильные слова говорит...
Массивы glued_* - координаты клеток с клеем. Должны заканчиваться на -1.
#include <stdio.h>
#include <stdlib.h>
#define M 100
#define N 200
int glued_Y[] = { 0, 1, -1 };
int glued_X[] = { 1, 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) {
char my_cube[6];
int dir, i;
char mask = 1 << in_cube[5];
if((x|y) < 0 || y >= M || x >= N || (SQ[y][x] & mask) || in_cube[5] == 0)
return;
SQ[y][x] |= mask;
if(SQ[M-1][N-1]) return;
for(dir = 0; dir < 4; dir++) {
for(i = 0; i < 6; i++)
my_cube[Cube_Step[dir][i]] = in_cube[i];
step(y + Y_Step[dir], x + X_Step[dir], my_cube);
}
}
char beg_cube[] = { 0, 1, 2, 3, 4, 5 };
void main() {
int i;
memset(&SQ, 0, M * N);
for(i = 0; glued_X[i] >= 0; i++)
SQ[glued_Y[i]][glued_X[i]] = -1;
step(0, 0, beg_cube);
puts(SQ[M-1][N-1]? "Found way\n" : "No ways\n");
}
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
