Страница 1 из 2

Олимпиадная задача

СообщениеДобавлено: 27 апр 2010, 18:07
Vladislav_133
В минувший понедельник на занятиях по олимпиадному программированию решали одну задачу. Мне показалась она интересной.
Собственно задача одна из многих на нахождение кратчайшего пути. В наших олимпиадах таких задач было несколько (см. http://shgpi.edu.ru/solver/).
Задача.
Пусть имеются две точки (x1,y1) и (x2,y2). Некто передвигается из первой точки во вторую. За один раз можно делать:
1. Шаг влево x-1
2. Шаг вправо x+1
3. Шаг вверх y+1
4. Шаг вниз y-1
1. Необходимо определить минимальное количество шагов от первой точки ко второй.
2. Найти все возможные маршруты с минимальным количеством шагов.

Собственно, если оставить только первый вопрос, то для нахождения минимального количества шагов программы писать не надо.
Действительно минимальное количество шагов можно вычислить по формуле abs(x1-x2) + abs(y1-y2). И все!
А вот что касается второго вопроса, то здесь без программы не обойтись. Типичная задача на нахождения самого короткого пути.
И типичнейшая же проблема - как в процессе перебора шагов отбрасывать пути, заведомо не ведущие к правильному результату.
В разных задачах этот критерий может быть разным. В данном случае критерий очевиден: если на очередном ходу расстояние до
целевой точки увеличилось, то этот шаг сразу следует аннулировать. Заметим, что если не вводить критерий, то движение
шагающего приведет скорее всего к переполнению стека. Вот собственно и все.
Код: Выделить всё
var
    x1,y1,x2,y2,i,j,n,min:integer;...
    r:integer;
    a:array[1..100] of integer;
    b:array[1..100] of integer;

procedure shag(x,y,rr:integer);
var
    rt:integer;
begin
    a[n]:=x; b[n]:=y; inc(n);
    if (x=x2) and (y=y2)  then
    begin
<------>if min>n-1 then min:=n-1;<----->
<------>for j:=1 to n-1 do.
<------>begin
<------>    write(a[j],' ',b[j],'; ');
<------>end;
<------>writeln;
    end
    else
    begin
<------>if rr>(x-x2)*(x-x2)+(y-y2)*(y-y2) then
<------>begin
<------>    rt:=(x-x2)*(x-x2)+(y-y2)*(y-y2);
<------>     shag(x+1,y,rt);.
<------>     shag(x,y+1,rt);.
<------>     shag(x-1,y,rt);.
<------>     shag(x,y-1,rt);.
<------>end;
    end;
    dec(n);
end;
{-------------------------------}....
begin
    readln(x1,y1);
    readln(x2,y2);
    for i:=1 to 100 do
    begin
<------>a[i]:=0;b[i]:=0;
    end;
    min:=200;
    if (not((x1=x2) and (y1=y2))) then
    begin<-----><------>
    r:=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    n:=1;
    shag(x1+1,y1,r);....
    n:=1;
    shag(x1,y1+1,r);....
    n:=1;
    shag(x1-1,y1,r);....
    n:=1;
    shag(x1,y1-1,r);....
    end
<------>else
<------> min:=0;<------>
    writeln(min);
end.



Остается только добавить, что вместо расстояния используется его квадрат, что, конечно, удобнее.
Заметим также, что в задаче предполагается, что минимальное количество шагов не может превзойти 100.
Обычное ограничение.

Замечание.
Однако вот вопрос. Нельзя ли улучшить алгоритм, основываясь на том факте, что минимальное количество шагов может быть вычислено заранее? Подумайте.

Re: Олимпиадная задача

СообщениеДобавлено: 27 апр 2010, 20:43
LMP
высказывать свои предположения можно всем, или нет?)

Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 08:58
Vladislav_133
Конечно всем.

Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 11:01
LMP
вы проверяете варианты движения во все стороны.

можно вычислить в какую стророну двигаться по оси x и y. по оси x двигаться двигаться до тех пор, пока положение обьекта и конечной точки по x не станет равным. по оси y аналогично. как только обьект достигает конечной точки, выводить путь. т.о. отбрасывается необходимость проверять в правильную ли сторону переместился обьект.

Код: Выделить всё
var
  len, p: integer;
  ax, ay: array [0..100] of integer;
  x, y, x1, y1, dx, dy, i: integer;

procedure next;
begin
  ax[p]:= x;
  ay[p]:= y;
  if (len = p) then begin
    for i:= 1 to p do begin
      write(ax[i], ' ', ay[i], '; ');
    end;
    writeln;
  end else begin
    p:= p+1;
    if (x <> x1) then begin
      x:= x+dx;
      next;
      x:= x-dx;
    end;
    if (y <> y1) then begin
      y:= y+dy;
      next;
      y:= y-dy;
    end;
    p:= p-1;
  end;
end;

begin
  readln(x, y);
  readln(x1, y1);
  p:= 0;
  len:= abs(x1-x)+abs(y1-y);
  if (x1 > x) then begin
    dx:= 1;
  end else begin
    dx:= -1;
  end;
  if (y1 > y) then begin
    dy:= 1;
  end else begin
    dy:= -1;
  end;
  next;
  writeln(len);
end.


но на небольших данных оба алгоритма работают быстро по сравнению со скоростью вывода мегабайт, или даже гигабайт данных в результате (если убрать вывод, то работают мгновенно, а с выводом могут работать минуты, и более).

Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 11:09
Vladislav_133
Хм, интересно. И все варианты выдает?

Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 11:13
LMP
да (неуверенно)

Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 11:16
Vladislav_133
А ты сравни мое решение и твое

Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 11:27
LMP
да, результат одинаковый, только в некоторых случаях порядок строк различен.

Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 11:30
LMP
хотя есть одно отличие, если начальные координаты и конечные равны, то в моём случае выводится пустая строка в начале. но это можно решить добавлением условия в основную программу, аналогичного вашему.

Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 11:34
LMP
код основной программы, в котором устранён вывод лишней строки:
Код: Выделить всё
begin
  readln(x, y);
  readln(x1, y1);
  len:= abs(x1-x)+abs(y1-y);
  if (len > 0) then begin
    p:= 0;
    if (x1 > x) then begin
      dx:= 1;
    end else begin
      dx:= -1;
    end;
    if (y1 > y) then begin
      dy:= 1;
    end else begin
      dy:= -1;
    end;
    next;
  end;
  writeln(len);
end.

Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 17:00
Vladislav_133
Кстати насчет моего вопроса, что нельзя ли использовать в качестве критерия уже известное заранее количество минимальных шагов. Можно. Т.е. на каждом шаге, если только мы не пришли в нужную точку, проверяем количество шагов. Если сравнялось, то отбрасываем шаг. Думаю, что таким способом задача решается, только алгоритм будет работать гораздо медленнее.

Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 17:39
vovan
Вот еще вариант.
Глубина рекурсии здесь будет похоже меньше.
Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int r=1,d=1;
int *ar; //массив для хранения направления движения, если в элементе находится 0, значит на этом шаге некто двигался по вертикали, если 1 то по горизонтали
int sx, sy; // начальные координаты
int len;

void find(int lenx, int leny, int pos) //параметры длина по x, по y и номер элемента массива куда следует записывать направление
{
    int i, j;
    int kx=sx, ky=sy;
    if (!leny || !lenx) {  //если по x или по y некто прошел весь путь, то есть осталось двигаться только по горизонтали или вертикали то все
        for (i=0; i<pos; i++) { /вычисляем координаты движения по направлению
            kx+=r*ar[i]; //если ar[i] не равен 0 то некто шел по горизонтали, если r==1 то вправо, если r==-1 то влево, прибавляем это к текущей координате по x
            ky+=d*(!ar[i]); //тоже самое что и с x, к текущей координате по y прибавляется 1, если ar[i]==0 и d=1; -1, если ar[i]==0 и d=-1; и 0 в случае если ar[i]!=0
            printf("%d %d; ", kx, ky);
        }
        if (!leny) //находим оставшиеся координаты, думаю условие можно убратьи оставить тоько циклы
            for (i=0;i<lenx; i++) {
                kx+=r;
                printf("%d %d; ", kx, ky);
            }
        else
            for (i=0;i<leny; i++) {
                ky+=d;
                printf("%d %d; ", kx, ky);
            }
        printf("\n");
        return;
    }
    for (i=leny; i>-1; i--) { //вычитаем из оставшегося направления по y значение i, заносим 0 в массив  и 1 единицу вычитаем 1 из оставшегося направления по x
        for (j=0;j<i;j++) {
            ar[j+pos]=0;
        }
        ar[i+pos]=1;
        find(lenx-1, leny-i, pos+i+1);
    }
}

int main(void)
{
    int x1,y1, x2,y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    sx=x1;
    sy=y1;
    if (x1==x2)
        if (y1==y2) {
            printf("0");  //случай, когда длна равна 0
            return 0;
        }
    if (x1>x2) r=-1; //если x1 > x2 то двигаться надо влево, то есть координата x уменьшается
    if (y1>y2) d=-1; //если y1 > y2 то двигаться вверх, y -уменьшается
    int lenx=abs(x1-x2); //расстояние по x
    int leny=abs(y1-y2);  //расстояние по y
    len=lenx+leny;
    ar=(int*)malloc(sizeof(int)*lenx*leny);
    find(lenx, leny, 0);
    printf("%d\n", len);
    return 0;
}


Re: Олимпиадная задача

СообщениеДобавлено: 28 апр 2010, 21:20
xdsl
vovan в своем репертуаре: код есть, объяснялок нема ;)
Вова, имейте жалость к форумчанам, здесь много студентов, которые только-только разбираться начали в хитросплетениях нетривиальных решений, а Вы их сразу по голове исходниками без единого комментария!

Re: Олимпиадная задача

СообщениеДобавлено: 29 апр 2010, 06:58
vovan
Я хотел обьяснение написать, только вот никак не удается придумать что написать. Сейчас комментарии хотя бы вставлю тогда

Re: Олимпиадная задача

СообщениеДобавлено: 29 апр 2010, 18:44
LMP
на мой взгляд в данной задаче есть ещё один интересный момент, узнать количество различных вариантов (путей), по которым можно добраться из первой точки до второй. мой алгоритм (при отсутсвии вывода путей, а только подсчёте их количества) на данных
Код: Выделить всё
0 0
15 15

работает приблизительно 10 секунд, получается 155177520 путей. с ограничением в 100 шагов максимальное количество путей получится на данных
Код: Выделить всё
0 0
50 50

и там будет очень большое число (не скажу какое, не считал ещё). но согласитесь и 10 секунд уже много если взять ограничение в 1 секунду ;) .

есть предложения, как можно уменьшить время подсчёта количества путей? (у меня есть вариант, но хочется выслушать предложения других :) )

Re: Олимпиадная задача

СообщениеДобавлено: 29 апр 2010, 19:44
vovan
Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ULL unsigned long long

ULL getsum(ULL *ar, int c)
{
    int i;
    int r=0;
    for (i=0;i<c;i++)
        r+=ar[i];
    return r;
}


int main(void)
{
    ULL *ar;
    int x, y, x1, y1;
    ULL sum;
    scanf("%d%d%d%d", &x, &y, &x1, &y1);
    int lenx=abs(x1-x);
    int leny=abs(y1-y);
    int len=lenx+leny;
    sum=1;
    ar=(ULL*)malloc(sizeof(ULL)*lenx);
    int i;
    for (i=0; i<lenx; i++) ar[i]=1;
    ULL r;
    ULL n, m;
    while (leny>0) {
        r=getsum(ar, lenx);
        n=ar[0];
        ar[0]=r;
        for (i=1;i<lenx; i++) {
            m=ar[i];
            ar[i]=ar[i-1]-n;
            n=m;
        }
        sum+=r;
        leny--;
    }
    printf("%llu\n%d\n", sum, len);
    return 0;
}


LMP, у тебя опечатка в количестве путей для 0 15 0 15?
у меня в обоих алгоритмах выдает число - 155117520

Re: Олимпиадная задача

СообщениеДобавлено: 29 апр 2010, 19:45
vovan
вот результат для 0 50 0 50
18446744072770573672(Не уверен, могло быть переполнение)
100

работает моментально
Суть алгоритма
Для случая когда при x=0, некто проходит весь путь вниз возможен только один вариант.
Записываем в сумму единицу
переменной I присваивае значение равное расстоянию по y
Дальше берем массив единиц. Количество элементов в массиве равно расстоянию по x
1. Подсчитываем их сумму и прибавляем к имеющейся сумме
2. В первый элемент массива заносим эту сумму. Каждый последующий элемент формируем из разности текущего значения предыдущего элемента и предыдущего значения предыдущего элемента.
3. уменьшаем количество I, и если I>0 то возвращаемся к первому шагу

Re: Олимпиадная задача

СообщениеДобавлено: 29 апр 2010, 21:45
LMP
LMP писал(а):LMP, у тебя опечатка в количестве путей для 0 15 0 15?

да, точно

Re: Олимпиадная задача

СообщениеДобавлено: 29 апр 2010, 22:04
LMP
для подсчёта количества путей нам достаточно знать dx и dy.

Код: Выделить всё
dy
5  |  1   6  21  56 126 252
4  |  1   5  15  35  70 126
3  |  1   4  10  20  35  56
2  |  1   3   6  10  15  21
1  |  1   2   3   4   5   6
0  |  1   1   1   1   1   1
---+-----------------------
   |  0   1   2   3   4   5 dx

(в таблице возможны опечатки, подсчёты производились вручную)

на пересечении значения dx и dy находится количество путей, как можно заметить оно равно сумме значения снизу и слева. т.о. два вложенных цикла достаточно для нахождения количества путей. грубо говоря всё что находится в отрицательных значениях dx и dy равно нулю, в позиции 0;0 - значение единица, и на основе этого значения строится вся оставшеяся часть поля.

Re: Олимпиадная задача

СообщениеДобавлено: 30 апр 2010, 09:21
xdsl
to LMP: красиво.

Re: Олимпиадная задача

СообщениеДобавлено: 30 апр 2010, 10:36
LMP
ещё бы, ручная работа :)

Re: Олимпиадная задача

СообщениеДобавлено: 30 апр 2010, 20:56
LMP
ещё немного отклонимся от начальной задачи.

найти минимальный путь из точки A в точку B, но дополнительно ограничим область некоторой картой, на которой будут непроходимые участки, и за пределы которой нельзя выходить. пример:

Код: Выделить всё
..........
...####...
...#..#...
...#......
...#..#...
...#..#...
...#B.#...
...####...
A.........
#........#

для данного примера один из ответов будет:

Код: Выделить всё
RRRRRRRUUUUULLLDDD

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

попробуйте обьединить обе подзадачи в один пробег :)

в качестве ограничений возьмём размер карты не более 100x100 клеток.

Re: Олимпиадная задача

СообщениеДобавлено: 01 май 2010, 18:13
vovan
на тесте 100x100 с небольшими препятствиями(непроходимая полоса чуть выше середины с одной проходимой клеткой по середине этой строки, A — в левом нижнем углу, B — в верхнем правом) выполняется за 2 секунды. Не знаю как можно еще сократить время
Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MSIZE 100
#define RSIZE MSIZE*MSIZE
#define MAXINT ((1<<(sizeof(int)*8-1))-1)

int max=MAXINT;

char mat[MSIZE][MSIZE+2];
int path[MSIZE][MSIZE];
char a[RSIZE+1];
char b[RSIZE+1];
int maxx, maxy;

void find(int x, int y, int cnt)
{

    if (cnt>=max) return;
    if (x<0 || y<0 || x>=maxx || y>=maxy) return;
    if (strchr("*#", mat[x][y])) return;
    if (cnt>=path[x][y]) return;
    path[x][y]=cnt;
    if (mat[x][y]=='B') {
        if (cnt<max) {
            memcpy(a, b, RSIZE*sizeof(char)); //в случае если путь короче предыдущего записывает его в основной массив
            max=cnt;
        }
        return;
    }

    char cc=mat[x][y];
    mat[x][y]='*';

    b[cnt]='U'; //записывает путь в резервный массив
    find(x-1, y, cnt+1);

    b[cnt]='L'; //записывает путь в резервный массив
    find(x, y-1, cnt+1);

    b[cnt]='D'; //записывает путь в резервный массив
    find(x+1, y, cnt+1);

    b[cnt]='R'; //записывает путь в резервный массив
    find(x, y+1, cnt+1);

    mat[x][y]=cc;
}

int main(void)
{
    char s[102], *p;
    int i=0, j, n;
    int x=-1,y=-1;
    while (!feof(stdin)) {
        n=scanf("%s", s);
        if (n<1) break;
        p=strchr(s, 'A');
        if (p) {
            y=p-s;
            x=i;
        }
        strcpy(mat[i++], s);
    }

    maxx=i;
    maxy=strlen(mat[0]);
    for (i=0; i<maxx; i++)
        for (j=0; j<maxy; j++)
            path[i][j]=MAXINT;
    if (x==-1 || y==-1) {
        printf("Invalid data\n");
        return 0;
    }
    find(x, y, 0);

    a[max]='\0';
    printf("%s\n%d", a, max);

    return 0;
}


Re: Олимпиадная задача

СообщениеДобавлено: 01 май 2010, 20:49
Vladislav_133
Ну народ раззодорился. Тряхнуть что ли и мне. Задачка интересная. Пока не пойму, как оптимально найти путь.

Re: Олимпиадная задача

СообщениеДобавлено: 01 май 2010, 21:29
LMP
у меня опять таки есть предположение, но решать ещё сам не пробовал.