Подскажите алгоритм для решения этой задачи
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;
}
|
|