VPF::Подскажите алгоритм для задачи

Abbath1349

Дата 29.10.2012, 08:55 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 214
Регистрация: 16.6.2010

Репутация: нет
Всего: нет

Подскажите алгоритм для решения этой задачи
http://acm.timus.ru/problem.aspx?space=1&num=1920

пробовал через dfs но там по времени не проходит

Код


#include <iostream>
#include <vector>

#define fip(a) for(int i=0;i<(a);i++)
#define fjp(b) for(int j=0;j<(b);j++)
using namespace std;
typedef vector<int> vi;
class task{
 struct cord{
  int i;
  int j;
  bool is_correct;
 };
 int N,L,size;
 int S,E;
 cord end;
 cord *ends;
 bool is_path;
 vi *g;
 cord *path;
 bool **visited;
 void read_data_from_file(){
  //FILE *file=fopen("input.txt","r");
  scanf("%d %d",&N,&L);
  //fclose(file);
  size=N*N;
  g=new vi[size];
  path=new cord[L];
  is_path=false;
  visited=new bool*[N];
  fip(N){
   visited[i]=new bool[N];
   fjp(N)
   visited[i][j]=false;
  }
 }
 /*void build_graph(){
  cord v;

  fip(size){
   fjp(4){
    v=get_vertex(i,j);
    if(v!=-1)
    g[i].push_back(v);
   }
  }
 // g[1].clear();
  fip(size){
   fjp(g[i].size())
    printf("%d ",g[i][j]+1);
   cout<<endl;
  }
 }*/
 void dfs(const cord &v,const int &l){
  path[l]=v;
  visited[v.i][v.j]=true;
  //printf("visit %d %d and L is %d\n",v.i+1,v.j+1,l);
  if(v.i==0&&v.j==1&&l==L-1){
   //printf("task was decided\n");
   is_path=true;
   return;
  } else if(l>L-1) return;
  cord t,last;
  bool was_attempt=false;
  fip(4){
   if(was_attempt) visited[last.i][last.j]=false;
   if(!is_path)
    t=get_vertex(v,i);
   
   if(is_correct(t)&&!visited[t.i][t.j]){
    was_attempt=true;
    last=t;
    dfs(t,l+1);
   }
  }
 }
 cord get_vertex(const cord &c,const int &n){
  int inc_1[4]={1,-1,0,0};
  int inc_2[4]={0,0,1,-1};
  cord t;
  t.i=inc_1[n]+c.i;
  t.j=inc_2[n]+c.j;
  
 
   return t;
  
 }
 bool is_correct(const cord &c){
  return (c.i>=0)&&(c.i<N)&&(c.j>=0)&&(c.j<N);
 }
public:
 void decide_task(){
  read_data_from_file();
//  build_graph();
  int i=0;
  cord c;
  c.i=0;
  c.j=0;
  if(L%2==0&&N*N>L){
   while(!is_path){
    dfs(c,0);
   }
   printf("Overwhelming power of magic\n");
   fip(L)
    printf("%d %d\n",path[i].i+1,path[i].j+1);
  }
  else printf("Unsuitable device\n");
 }
};
int main(){
 task t;
 t.decide_task();
 system("pause");
 return 0;
}

Это сообщение отредактировал(а) Abbath1349 - 29.10.2012, 08:56

Lipetsk

Дата 29.10.2012, 11:03 (ссылка)

(нет голосов)

Загрузка ...

в форме ;)

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 28.1.2009
Где: Липецк

Репутация: 2
Всего: 5

не очень понял, что требуется
найти любой цикл? тогда это элементарно

Abbath1349

Дата 29.10.2012, 11:38 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 214
Регистрация: 16.6.2010

Репутация: нет
Всего: нет

Цитата(Lipetsk @ 29.10.2012, 11:03)

не очень понял, что требуется
найти любой цикл? тогда это элементарно

Найти цикл заданной длины например как в примере есть поле 3 х 3 нужно найти цикл длинной 6 из клетки 0 0

Silent

Дата 31.10.2012, 08:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

Может быть вот эта ссылка вам поможет
И если получите АС - отпишитесь об алгоритме

Это сообщение отредактировал(а) Silent - 31.10.2012, 08:37

Lipetsk

Дата 31.10.2012, 10:04 (ссылка)

(нет голосов)

Загрузка ...

в форме ;)

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 28.1.2009
Где: Липецк

Репутация: 2
Всего: 5

Цитата(Abbath1349 @ 29.10.2012, 09:38)

Цитата(Lipetsk @ 29.10.2012, 11:03)

не очень понял, что требуется
найти любой цикл? тогда это элементарно

Найти цикл заданной длины например как в примере есть поле 3 х 3 нужно найти цикл длинной 6 из клетки 0 0

ну так обходите по периметру или змейкой сразу двигаясь двумя концами

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »