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

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

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

Сообщение vovan 02 май 2010, 11:59

Немного изменил программу, сейчас направление пути вычисляется в зависимости от того в каком направлении находится конечная точка. На тесте на котором кото прошлая программа работает 2 секунды - эта работает за полсекунды(input_2 в архиве). Но в случае если путь проложить невозможно все еще больше 2 секунд(input_4 в архиве)
Код: Выделить всё
#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;
int ex, ey;

void set_dirs(char *dir, int dx, int dy)
{
    int sxel, exel, syel, eyel;
    if (dy==0) {
        sxel=0;
        exel=2;
        syel=1;
        eyel=3;
    } else {
        sxel=1;
        exel=3;
        syel=0;
        eyel=2;
    }
    if (dy<0) {
        dir[syel]='L';
        dir[eyel]='R';
    } else {
        dir[syel]='R';
        dir[eyel]='L';
    }
    if (dx<0) {
        dir[sxel]='U';
        dir[exel]='D';
    } else {
        dir[sxel]='D';
        dir[exel]='U';
    }
}


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

    if (cnt>=max) return 0;
    if (x<0 || y<0 || x>=maxx || y>=maxy) return 0;
    if (strchr("*#", mat[x][y])) return 0;
    if (cnt>=path[x][y]) return 0;
    path[x][y]=cnt;
    if (mat[x][y]=='B') {
        if (cnt<max) {
            memcpy(a, b, RSIZE*sizeof(char));
            max=cnt;
        }
        return 1;
    }

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

    int r=0, i;
    char dir[4];
    set_dirs(dir, ex-x, ey-y);

    for (i=0;i<4;i++) {
        b[cnt]=dir[i];
        if (dir[i]=='U')
            r=find(x-1, y, cnt+1) || r;
        if (dir[i]=='L')
            r=find(x, y-1, cnt+1) || r;
        if (dir[i]=='D')
            r=find(x+1, y, cnt+1) || r;
        if (dir[i]=='R')
            r=find(x, y+1, cnt+1) || r;
    }

    mat[x][y]=cc;
    return r;
}

int main(void)
{
    char s[102], *p;
    int i=0, j, n;
    int x=-1,y=-1;
    ey=-1;
    ex=-1;
    while (!feof(stdin)) {
        n=scanf("%s", s);
        if (n<1) break;
        p=strchr(s, 'A');
        if (p) {
            y=p-s;
            x=i;
        }
        p=strchr(s, 'B');
        if (p) {
            ey=p-s;
            ex=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 || ey==-1 || ex==-1) {
        printf("Invalid data\n");
        return 0;
    }
    int res;
    res=find(x, y, 0);

    if (res) {
        a[max]='\0';
        printf("%s\n%d", a, max);
    }
    else printf("Path not found\n");

    return 0;
}

Вложения
test.tar.gz
(40 Кб) Скачиваний: 319
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

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

Сообщение Vladislav_133 02 май 2010, 17:43

Внесу и я свою лепту в решение. Долго думал, как принцип минимизации (т.е. очередной шаг должен сокращать расстояние) применить в случае наличия препятствий. Придумал следующее. Пока нет препятствия, то действует принцип минимизации. Если при очередном шаге попадаешь на препятствие, то клетку с которой ты попадал на препятствие помечаем. Это значит, что прыжки с этой клетки не подвержены принципу минимизации. Надо еще по анализировать реальный выигрышь, но мне кажется он значительный. Вот программа на Си. Программа получилась длинноватой, но я доволен. Вот это действительно праздник!

Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <wchar.h>
#include <errno.h>
#include <sys/stat.h>
#include <malloc.h>
#include <unistd.h> 

void step(int,int,int,int,int);

int n,pr,k,min,x2,y2,shn;
char * fi,* fi1, c;
int *a,*b, *a1,*b1;
char s[10];
int main()
{
    int i,j,x1,y1,r1;
    fscanf(stdin,"%d",&n);
    if(n>0&&n<101)
    {
   fi=(char*)malloc(n*n);
   a=(int*)malloc(sizeof(int)*n*n);
   b=(int*)malloc(sizeof(int)*n*n);
   a1=(int*)malloc(sizeof(int)*n*n);
   b1=(int*)malloc(sizeof(int)*n*n);
   fi1=(char*)malloc(n*n);
    }else
    {
   fprintf(stdout,"Error!\n");
   return 1;
    }
//
    i=0;
    while(true)
    {
       fscanf(stdin,"%c",&c);
       if(c<=32)continue;
       *(fi+i)=c; *(fi1+i)='-';
       a[i]=0; b[i]=0; a1[i]=0; b1[i]=0;
       if(c=='A')
       {
      x1=i%n; y1=i/n;
       }
       if(c=='B')
       {
      x2=i%n; y2=i/n;
       }
       i++;
       if(i==n*n)break;
    }
//
    pr=0;
    min=n*n;
    shn=abs(x1-x2)+abs(y1-y2);
    r1=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    k=0;  if(x1<n-1)step(x1,1,y1,0,r1);
    k=0;  if(y1<n-1)step(x1,0,y1,1,r1);
    k=0;  if(x1>0)step(x1,-1,y1,0,r1);
    k=0;  if(y1>0)step(x1,0,y1,-1,r1);

    if(pr==1)
    {
   fprintf(stdout,"%d\n",min);
   for(i=0; i<min; i++) fprintf(stdout,"%d %d;",a1[i],b1[i]);
   fprintf(stdout,"\n");
    }
    else
    {
   fprintf(stdout,"No pass\n");
    }
    free(fi);free(a); free(b);free(fi1);
    return 0;
}
//
void step(int x,int dx,int y,int dy,int r)
{
    int xx,yy,rr,i;
    xx=x+dx; yy=y+dy;
    if(*(fi+xx+yy*n)=='q'||min==shn||k+1>min)
    {
   return;
    }
    a[k]=xx;  b[k]=yy;
    if(*(fi+xx+yy*n)=='#')
    {   
   *(fi1+x+y*n)='+';
   return;
    };
    if(*(fi+xx-1+yy*n)=='#'||*(fi+xx+1+yy*n)=='#'||*(fi+xx+(yy+1)*n)=='#'||*(fi+xx+(yy-1)*n)=='#')
    {
   *(fi1+xx+yy*n)='+';   
    }
    k++;
    if((*(fi+xx+yy*n)=='B'))
    {
   pr=1;
   if(min>k)
   {
       min=k;
       for(i=0; i<k; i++)
       {
      a1[i]=a[i]; b1[i]=b[i];
       }
   }
   k--;    
   return;
    };
    rr=(xx-x2)*(xx-x2)+(yy-y2)*(yy-y2);
    if(rr<r||*(fi1+x+y*n)=='+')
    {
       *(fi+xx+yy*n)='q';
        if(xx<n-1)step(xx,1,yy,0,rr);
        if(yy<n-1)step(xx,0,yy,1,rr);
        if(xx>0)step(xx,-1,yy,0,rr);
        if(yy>0)step(xx,0,yy,-1,rr);
        *(fi+xx+yy*n)='.';
    }
    k--;
}
//



Исправлено
Последний раз редактировалось Vladislav_133 03 май 2010, 11:10, всего редактировалось 3 раз(а).
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение vovan 02 май 2010, 18:53

Ваш код на тесте который приводил Денис, выдает не минимальный результат
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

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

Сообщение Vladislav_133 02 май 2010, 19:33

Поглядим
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение Vladislav_133 02 май 2010, 23:35

Программу исправил (выше уже исправленный код). Теперь кажется работает (т.е. ищет минимальный путь). Но разочарован. Работает медленно. Так что 2 - й и 4-й денисов тест пришлось проверять в уменьшенном масштабе. Будем работать над оптимизацией.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение Vladislav_133 03 май 2010, 11:12

Нашел возможность оптимизации. Но пока тесты 2 и 4 все равно выполняются медленно.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение vovan 03 май 2010, 12:00

В архиве еще два теста.
Ваш код на них выдает nopass.
Судя по всему это из-за того что при единственном возможном ходе расстояние до конечной точки увеличивается. Может стоит учесть решетки по диагонали?
Вложения
test.tar.gz
(10 Кб) Скачиваний: 327
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

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

Сообщение vovan 03 май 2010, 13:39

Владислав Юрьевич, прошу прощения что взял вашу идею, на ее основе модифицировал свой код, теперь все тесты проходит менее чем за десятую секунды. Не знаю стоит ли его вставлять сюда.
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

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

Сообщение Vladislav_133 03 май 2010, 13:46

Вот что значит независимый тестировщик. Ты прав, надо и угловые элементы использовать.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение vovan 03 май 2010, 13:49

Нашел еще одну проблему(11 тест) минимальное количество шагов 21, ваш код выдает 27 как и мой с вашей идеей об учете препятствий.
Вложения
test.tar.gz
(693 байт) Скачиваний: 349
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

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

Сообщение vovan 03 май 2010, 13:56

Что если пометить + области окруженные с трех сторон при отсутствии в них конечной точки, или возможно даже с двух.
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

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

Сообщение Vladislav_133 03 май 2010, 13:58

Подумаем. А 10 тест идет правильно. Надо подумать.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение Vladislav_133 03 май 2010, 14:23

Опубликую вариант, которым сейчас пользуюсь. Требуется еще оптимизация + в 11 тесте дает больше шагов.

Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <wchar.h>
#include <errno.h>
#include <sys/stat.h>
#include <malloc.h>
#include <unistd.h> 

void step(int,int,int,int,int);

int n,pr,k,min,x2,y2,shn;
char * fi,* fi1, c;
int *a,*b, *a1,*b1;
char s[10];
int main()
{
    int i,j,x1,y1,r1;
    fscanf(stdin,"%d",&n);
    if(n>0&&n<101)
    {
   fi=(char*)malloc(n*n);
   a=(int*)malloc(sizeof(int)*n*n);
   b=(int*)malloc(sizeof(int)*n*n);
   a1=(int*)malloc(sizeof(int)*n*n);
   b1=(int*)malloc(sizeof(int)*n*n);
   fi1=(char*)malloc(n*n);
    }else
    {
   fprintf(stdout,"Error!\n");
   return 1;
    }
//
    i=0;
    while(true)
    {
       fscanf(stdin,"%c",&c);
       if(c<=32)continue;
       *(fi+i)=c; *(fi1+i)='-';
       a[i]=0; b[i]=0; a1[i]=0; b1[i]=0;
       if(c=='A')
       {
      x1=i%n; y1=i/n;
       }
       if(c=='B')
       {
      x2=i%n; y2=i/n;
       }
       i++;
       if(i==n*n)break;
    }
//
    pr=0;
    min=n*n*n;
    shn=abs(x1-x2)+abs(y1-y2);
    r1=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    k=0;  if(x1<n-1)step(x1,1,y1,0,r1);
    k=0;  if(y1<n-1)step(x1,0,y1,1,r1);
    k=0;  if(x1>0)step(x1,-1,y1,0,r1);
    k=0;  if(y1>0)step(x1,0,y1,-1,r1);

    if(pr==1)
    {
   fprintf(stdout,"%d\n",min);
   for(i=0; i<min; i++) fprintf(stdout,"%d %d;",a1[i],b1[i]);
   fprintf(stdout,"\n");
    }
    else
    {
   fprintf(stdout,"No pass\n");
    }
    free(fi);free(a); free(b);free(fi1);
    return 0;
}
//
void step(int x,int dx,int y,int dy,int r)
{
    int xx,yy,rr,i;
    xx=x+dx; yy=y+dy;
    if(*(fi+xx+yy*n)=='q'||min==shn||k+1>min)
    {
   return;
    }
    a[k]=xx;  b[k]=yy;
    if(*(fi+xx+yy*n)=='#')
    {   
   *(fi1+x+y*n)='+';
   return;
    };
    if((*(fi+xx-1+yy*n)=='#'||*(fi+xx+1+yy*n)=='#'||*(fi+xx+(yy+1)*n)=='#'||*(fi+xx+(yy-1)*n)=='#')||(*(fi+xx-1+(yy-1)*n)=='#'||*(fi+xx+1+(yy+1)*n)=='#'||*(fi+xx+1+(yy-1)*n)=='#'||*(fi+xx-1+(yy+1)*n)=='#'))
    {
       *(fi1+xx+yy*n)='+';   
    }
    k++;
    if((*(fi+xx+yy*n)=='B'))
    {
   pr=1;
   if(min>k)
   {
       min=k;
       for(i=0; i<k; i++)
       {
      a1[i]=a[i]; b1[i]=b[i];
       }
   }
   k--;    
   return;
    };
    rr=(xx-x2)*(xx-x2)+(yy-y2)*(yy-y2);
    if(rr<r||*(fi1+x+y*n)=='+')
    {
       *(fi+xx+yy*n)='q';
        if(xx<n-1)step(xx,1,yy,0,rr);
        if(yy<n-1)step(xx,0,yy,1,rr);
        if(xx>0)step(xx,-1,yy,0,rr);
        if(yy>0)step(xx,0,yy,-1,rr);
        *(fi+xx+yy*n)='.';
    }
    k--;
}

Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение vovan 03 май 2010, 18:06

Решил проблему с 11 тестом путем запрета на посещение всех областей закрытых с трех сторон.
Код: Выделить всё
#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;
int ex, ey;

void set_dirs(char *dir, int dx, int dy)
{
    int sxel, exel, syel, eyel;
    if (dy==0) {
        sxel=0;
        exel=2;
        syel=1;
        eyel=3;
    } else {
        sxel=1;
        exel=3;
        syel=0;
        eyel=2;
    }
    if (dy<0) {
        dir[syel]='L';
        dir[eyel]='R';
    } else {
        dir[syel]='R';
        dir[eyel]='L';
    }
    if (dx<0) {
        dir[sxel]='U';
        dir[exel]='D';
    } else {
        dir[sxel]='D';
        dir[exel]='U';
    }
}

void fill_mat(int x, int x1, int y, int y1, int xx)
{
    if (xx) { if ((x1-x)<=1) return; }
    else     if ((y1-y)<=1) return;
    int i;
    if (xx) {
        for (i=x+1;i<x1;i++) if (mat[i][y]=='A' || mat[i][y]=='B') return;
        for (i=x+1;i<x1;i++) mat[i][y]='#';
    }
    else {
        for (i=y+1;i<y1;i++) if (mat[x][i]=='A' || mat[x][i]=='B') return;
        for (i=y+1;i<y1;i++) mat[x][i]='#';
    }
}

void modify(int x, int y)
{
    int st=0;
    int stx=x, sty=y;
    int i, d;
    if (y<maxy-1) {
        d=x;
        if (x>0) d--;
        for (i=d; i<maxx; i++) {
            if (mat[i][y+1]=='#') {
                if (st==0) {
                    st=1;
                    stx=i;
                } else fill_mat(stx, i, y+st, y, 1);
            } else
                if (mat[i][y]!='#')  break;
        }
    }

    if (y>1) {
        st=0;
        d=x;
        if (x>0) d--;
        for (i=d; i<maxx; i++) {
            if (mat[i][y-1]=='#') {
                if (st==0) {
                    st=-1;
                    stx=i;
                } else fill_mat(stx, i, y+st, y, 1);
            } else
                if (mat[i][y]!='#') break;
        }
    }

    if (x<maxx-1) {
        st=0;
        d=y;
        if (d>0) d--;
        for (i=d; i<maxy; i++) {
            if (mat[x+1][i]=='#') {
                if (st==0) {
                    st=1;
                    sty=i;
                } else fill_mat(x+st, x, sty, i, 0);
            } else
                if (mat[x][i]!='#') break;
        }
    }

    if (x>1) {
        st=0;
        d=y;
        if (d>0) d--;
        for (i=d; i<maxy; i++) {
            if (mat[x-1][i]=='#') {
                if (st==0) {
                    st=-1;
                    sty=i;
                } else fill_mat(st+x, x, sty, i, 0);
            } else
            if (mat[x][i]!='#') break;
        }
    }
}

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

    int len=abs(ex-x)+abs(ey-y);
    if (cnt>=max) return 0;
    if (x<0 || y<0 || x>=maxx || y>=maxy) return 0;
    if (strchr("*#", mat[x][y])) return 0;
    if (cnt>=path[x][y]) return 0;
    path[x][y]=cnt;
    if (mat[x][y]=='B') {
        if (cnt<max) {
            memcpy(a, b, RSIZE*sizeof(char));
            max=cnt;
        }
        return 1;
    }
    if (len>size) {
        int boo=1;
        if (x>0)                      if (mat[x-1]  [y]=='#') boo=0;
        if (y>0)                      if (mat[x]  [y-1]=='#') boo=0;
        if (x<maxx-1)                 if (mat[x+1]  [y]=='#') boo=0;
        if (y<maxy-1)                 if (mat[x]  [y+1]=='#') boo=0;
        if (x>0 && y>0)               if (mat[x-1][y-1]=='#') boo=0;
        if (x>0 && y<(maxy-1))        if (mat[x-1][y+1]=='#') boo=0;
        if (x<(maxx-1) && y>0)        if (mat[x+1][y-1]=='#') boo=0;
        if (x<(maxx-1) && y<(maxy-1)) if (mat[x+1][y+1]=='#') boo=0;
        /*if (inroom(x, y)) boo=0;*/
        if (boo) return 0;
    }

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

    int r=0, i;
    char dir[4];
    set_dirs(dir, ex-x, ey-y);

    for (i=0;i<4;i++) {
        b[cnt]=dir[i];
        if (dir[i]=='U')
            r=find(x-1, y, cnt+1, len) || r;
        if (dir[i]=='L')
            r=find(x, y-1, cnt+1, len) || r;
        if (dir[i]=='D')
            r=find(x+1, y, cnt+1, len) || r;
        if (dir[i]=='R')
            r=find(x, y+1, cnt+1, len) || r;
    }

    mat[x][y]=cc;
    return r;
}

int main(void)
{
    char s[102], *p;
    int i=0, j, n;
    int x=-1,y=-1;
    ey=-1;
    ex=-1;
    while (!feof(stdin)) {
        n=scanf("%s", s);
        if (n<1) break;
        p=strchr(s, 'A');
        if (p) {
            y=p-s;
            x=i;
        }
        p=strchr(s, 'B');
        if (p) {
            ey=p-s;
            ex=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 || ey==-1 || ex==-1) {
        printf("Invalid data\n");
        return 0;
    }
    for (i=0; i<maxx; i++)
        for (j=0; j<maxy; j++)
            if (mat[i][j]=='#') modify(i,j);

    for (i=maxx-1; i>=0; i--)
        for (j=maxy-1; j>=0; j--)
            if (mat[i][j]=='#') modify(i,j);

    for (i=0; i<maxx; i++) {
        for (j=0; j<maxy; j++)
            fprintf(stderr, "%c", mat[i][j]);
        fprintf(stderr, "\n");
    }

    int res;
    int len=abs(ey-y)+abs(ex-x);
    res=find(x, y, 0, len);

    if (res) {
        a[max]='\0';
        printf("%s\n%d", a, max);
    }
    else printf("Path not found\n");

    return 0;
}

Последний раз редактировалось vovan 03 май 2010, 20:40, всего редактировалось 2 раз(а).
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

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

Сообщение Vladislav_133 03 май 2010, 18:38

Программы разрастаются
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение Vladislav_133 03 май 2010, 20:17

Тоже нашел способ обойти 11 тест, но алгоритм стал в некоторых случаях жутко медленным. В общем завтра продолжим.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Пред.

Вернуться в Алгоритмизация и программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron