Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C&C++] Виртуальный робот в лабиринте

Автор: student117 17.8.2011, 01:43

Робот идёт по лабиринту размером X на Y.
Начинает всегда в координате (1,0) (т.е. (1,0) всегда коридор).
labirint[x][y] == 0 - стена
labirint[x][y] == 1 - коридор
Выход - 1 на краю лабиринта.
Программа должна выводить координаты маршрута в виду (x1,y1)(x2,y2)...(xN,yN)

Пример:
0,1,0,0,0,0,
0,1,1,1,0,0,
0,0,0,1,1,0,
0,1,1,1,0,0,
0,1,0,1,1,0,
0,1,0,0,0,0,
Решение: (1,0)(1,1)(2,1)(3,1)(3,2)(3,3)(2,3)(1,3)(1,4)(1,5)

Предпочтения:
Алгоритм должен быть как можно проще.
Читабельность важнее производительности.
Как можно меньше спецефичного С++ кода.

Я довел это до:

Код


unsigned short move_robot(short x, short y)
{ 
    // За пределами?
    if (x < 0 || x > MAX_X || y < 0 || y > MAX_Y)
    {
        return FALSE;
    }

    // Нашли выход и это не вход? 
    if (labirint[y][x] == 1 && (x != 1 && y != 0) && 
       (x == 0 || x == MAX_X-1 || y == 0 || y == MAX_Y-1))
    {
        labirint[y][x] = 4;
        return TRUE;
    }
 
    // Это не корридор?
    if (labirint[y][x] != 1)
    {
        return FALSE;
    }
 
    // Пометим как маршрут
    labirint[y][x] = 2;
 
    // Север
    if (move_robot(x, y-1) == TRUE)
    {
        return TRUE;
    }
 
    // Юг
    if (move_robot(x, y+1) == TRUE)
    {
        return TRUE;
    }

     // Запад
    if (move_robot(x-1, y) == TRUE)
    {
        return TRUE;
    }
 
    // Восток
    if (move_robot(x+1, y) == TRUE)
    {
        return TRUE;
    }
 
    // Пометим, что по этому маршруту ходить больше не надо
    labirint[y][x] = 3;
 
    return FALSE;
}

void print_solution(void)
{
    unsigned short y;
    unsigned short x;
 
 
    for (y = 0; y < MAX_Y; y++)
    {
        for (x = 0; x < MAX_X; x++)
        {
            if (labirint[y][x] == 2)
            {
                printf("(%d,%d)", x, y);
            }
            else if (labirint[y][x] == 4)
            {
                printf("(%d,%d)\n", x, y);
                printf("Exit at (%d,%d)\n", x, y);
            }
        }
    }
}

Код находит нужное решение при вызове move_robot(1, 0).

Моя проблема в том, что print_solution() выводит:
(1,0)(1,1)(2,1)(3,1)(3,2)(1,3)(2,3)(3,3)(1,4)(1,5)
Т.е. координаты "перепутаны", когда робот идёт с Запада на Восток. Аналогично будет если маршрут на выход будет с Юга на Север.

Есть идеи?
Сортировка?
Или надо перерабатывать алгоритм?

Спасибо.

Автор: t_gran 17.8.2011, 10:00

student117, всё довольно просто. Сохраняйте пройденный путь в стеке. Стек можете сами реализовать, либо воспользоваться STL. Вот что у меня получилось исходя из вашего кода:

Код


#include <cstdio>
#include <stack>

#define MAX_X 6
#define MAX_Y 6

unsigned labirint[MAX_Y][MAX_X] = {{0,1,0,0,0,0},
                                   {0,1,1,1,0,0},
                                   {0,0,0,1,1,0},
                                   {0,1,1,1,0,0},
                                   {0,1,0,1,1,0},
                                   {0,1,0,0,0,0}};

struct TCoord
{
   short x, y;
};
                                   
std::stack<TCoord> stack;

//----------------------------------------------//
bool move_robot(short x, short y,
                short fx, short fy)
{
   if (x < 0 || x > MAX_X || y < 0 || y > MAX_Y)
   {
      return false;
   }

   // Это не корридор?
   if (labirint[y][x] != 1)
   {
      return false;
   }

   TCoord coord = {x, y};
   stack.push(coord);
   
   // Нашли выход и это не вход?
   if ((labirint[y][x] == 1) && (x == fx) && (y == fy))
   {
      labirint[y][x] = 4;
      return true;
   }

   // Пометим как маршрут
   labirint[y][x] = 2;
   
   // Север
   if (move_robot(x, y - 1, fx, fy) == true)
   {
      return true;
   }

   // Юг
   if (move_robot(x, y + 1, fx, fy) == true)
   {
      return true;
   }
   // Запад
   if (move_robot(x - 1, y, fx, fy) == true)
   {
      return true;
   }

   // Восток
   if (move_robot(x + 1, y, fx, fy) == true)
   {
      return true;
   }

   labirint[y][x] = 3;
   stack.pop();
   
   return false;
}
//----------------------------------------------//
void print_solution()
{
   while (stack.empty() == false)
   {
      printf("(%d,%d)", stack.top().x, stack.top().y);
      stack.pop();
   }
}
//----------------------------------------------//
int main()
{
   move_robot(1, 5, 1, 0);
   print_solution();

   return 0;
}

Правда путь выводится в обратном порядке, но для этого есть очередь. Ведь так?! smile

http://codepad.org/WZTMWtq0

Автор: student117 17.8.2011, 11:16

спасибо, t_gran
не успел пока разобраться/вникнуть, но первая реакция:
1. Stack на STL может быть посчитан за C++. Предпочтение отдаётся коду с наименьшим спецфичным С++ синтаксисом.
2. По всей видимости код использует координаты выхода. Условием задачи координаты вызода не даны.

Автор: student117 17.8.2011, 14:24

да, стэк работает.
в исходном коде на 25ой строке простое

Код


solution[i].x = x;
solution[i].y = y;
i++;

и на 52ой

Код


i--;

делают то что нужно. smile

Разумеется по хорошему нужно делать StackPush(), StackPop(), IsStackFull(), IsStackEmpty() функционал.
Просто добавлять эти строки не безопасно.

t_gran, спасибо ещё раз за наводку.

Автор: Silent 17.8.2011, 16:06

Для поставленной задачи необходимо использовать другой алгоритм - поиск не в глубину, а в ширину:

Код


#include <stdio.h>

const int N = 10;
int dx[4] = {-1,0,1,0},
    dy[4] = {0,-1,0,1};

int labirint[N][N];
int qx[N*N], qy[N*N], pred[N*N];
int head = 0, tail = 0;
int n;

void init()
{
    scanf("%d",&n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d",&labirint[i][j]);
}

void out(int x)
{
    if (pred[x] == -1) printf("(0,1) ");
    else
    {
        out(pred[x]);
        printf("(%d,%d) ",qy[x]-1,qx[x]-1);
    }
}

bool solve()
{
    qx[0] = 1;
    qy[0] = 2;
    pred[0] = -1;
    bool F = true;
    while ((head <= tail) && F)
    {
        labirint[qx[head]][qy[head]] = head+2;
        for (int i = 0; i < 4; i++)
        {
            int kx = qx[head] + dx[i],
                ky = qy[head] + dy[i];
            if (labirint[kx][ky] == 1)
            {
                if (kx == n) F = false;
                tail++;
                qx[tail] = kx;
                qy[tail] = ky;
                pred[tail] = head;
            }
        }
        head++;
    }
    return !F;
}

void main()
{
    freopen("in.txt", "rt", stdin);
    freopen("out.txt", "wt", stdout);
    init();
    if (solve()) out(tail);
}

легко переделывается в чистый С (мне так кажется, хотя ни разу его не знаю)