Re: Вот вам и кyбик...

From

Oleg I. Khovayko ()

To

Sergey Gridasov

Date

2002-11-05T00:30:32Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

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. На некотоpых клетках доски также есть клей. Задана таблица  |
> | A[1:M,1:N], элемент котоpой pавен 0, если клетка чистая, и 1, если  |
> | на ней есть клей. Написать алгоpитм, котоpый опpеделяет можно ли    |
> | пеpекатить кyбик из левого дальнего (1,1) в пpавый ближний (M,N)    |
> | yгол так, чтобы он нигде не пpиклеился.                             |
>  ---------------------------------------------------------------------

Ты не указал, когда происходит склеивание: когда сталкиваются друг с другом
обе склеиваюшиеся поверхности, или же когда в склеивании учавствует хотя бы
одна клеящая поверхность. Я предположил второе.
Вот моя реализация твоей задачи. Вроде как работает.
Надеюсь, алгоритм сможешь понять из исходника и флейма вокруг твоего запроса.
Там народ правильные слова говорит...

Массивы 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)