Page 2 of 3
Posted: Thu Oct 27, 2005 9:22 am
by Dominik Michniewski
Mf, how did you compute 19 in 2nd case ?
Code: Select all
7 11
.....1.....
...........
...........
...........
2....3....4
...........
...........
I modified sample to easiest reading text below.
Distance matrix is as folow
Code: Select all
|1 2 3 4
-+----------
1|0 5 4 5
2|5 0 5 10
3|4 5 0 5
4|5 10 5 0
Best route is, I think, 1-2-3-4-1 or 1-4-3-2-1, both of length 20.
Could you show me route of length 19, starting and ending in 1 ?
Best regards
DM
Posted: Thu Oct 27, 2005 9:38 am
by mf
Actually, that CodeMaker's test was not correct. My program interpreted it as if it was the first test below.
For this input:
Code: Select all
11 7
.....L.
.......
.......
.......
.......
.......
..#....
#....#.
.......
.......
.......
7 11
.....L.....
...........
...........
...........
#....#....#
...........
...........
the output should be: 19, 20.
Posted: Thu Oct 27, 2005 9:58 am
by Dominik Michniewski
Thanks for reply
I thought, that there must be any easy explanation
And could you tell me right answer for cases:
Code: Select all
10 10
..........
..#....#..
..#....#..
..#....#..
..##L###..
..#....#..
..#....#..
..........
..........
..........
10 10
#..#..#..#
..........
..........
#..L..#..#
..........
..........
#..#..#..#
..........
..........
#..#..#..#
??
My program outputs:
22
48
Best regards
DM
Posted: Thu Oct 27, 2005 11:39 am
by Cho
My program gives the same output.
Posted: Sat Nov 05, 2005 12:32 am
by w k
Try the input like this:
2 2
L.
..
The correct output is 0. At least it was my problem. Have AC!
Wojciech
Posted: Mon Nov 14, 2005 4:31 am
by DongJoo Kim
There is another approach. What I did was SA(Simulated Annealing).
Just calculate the cost function.
Cost function would be the order of visiting each nuts.
Posted: Mon Nov 14, 2005 6:45 am
by yatsen
DongJoo Kim wrote:There is another approach. What I did was SA(Simulated Annealing).
Just calculate the cost function.
Cost function would be the order of visiting each nuts.
How to prove this?
Posted: Mon Nov 14, 2005 7:25 am
by yatsen
I got a lot of WA for this problem.
Can anyone post more test I/O?
Thanks.
Posted: Mon Nov 14, 2005 1:01 pm
by DongJoo Kim
yatsen wrote:DongJoo Kim wrote:There is another approach. What I did was SA(Simulated Annealing).
Just calculate the cost function.
Cost function would be the order of visiting each nuts.
How to prove this?
For the answer, I surf the web and read the article about the prove of SA(Simulated Annealing). However, I can't understand.
Only one thing I know is that the value will be converged to the proper answer as long as we have enough N(iteration) and T(temparture- uncertainty).
I do not want to recommend to use this algorithm first. However, if there is nothing you can do, SA can be the final choice.
Posted: Fri Nov 18, 2005 12:27 am
by technobug
i read the pdf and found it nice but i dont know how to implement it without looking like backtracking.... anyone can give me a hint?
Posted: Mon Nov 21, 2005 6:18 pm
by yatsen
Cho wrote:My solution tries all possible visiting orders of the nuts by a DFS with 2 hueristics to cut off. The first one is to cut off if the current cost plus the under-estimated future cost is not less than minimum cost. The second one is not to visit the k-th nut from the i-th nut if there is a j-th nut such that the j-th nut is not visited yet and cost(i->j)+cost(j->k)<=cost(i->k).
I use your method but I got WA. Can anyone help?
Here is my code:
Code: Select all
#include <stdio.h>
#include <string.h>
#define Max 21
#define Maxint 2147483647
typedef struct
{
int x,y;
}Node;
Node nut[15];
int Row,Column,used[Max],seq[Max],D[16][16],check[16][16];
char map[Max][Max];
int n,Lx,Ly,min;
int distance(int x1,int y1,int x2,int y2)
{
int x=abs(x1-x2), y=abs(y1-y2);
return (x>y ? x:y);
}
int checkshort(int i,int j)
{
int k,a,b,c;
for(k=0; k<n; k++)
{
if(k==i || k==j ) continue;
a=D[i][k];
b=D[k][j];
c=D[i][j];
if(a+b<=c)
return 0;
}
return 1;
}
void dfs(int i,int k,int v)
/* i: dfs from this node, k:the rank in seq[], v: path length so far */
{
int j,v2,t;
v2=D[seq[k-1]][n];
if(v+v2>=min)
return;
if(k==n+1)
{
v+=v2;
if(v<min) min=v;
return;
}
for(j=0; j<n; j++)
{
if(used[j]) continue;
if(!check[i][j])
{
for(t=0; t<n; t++)
{
if(t==i || t==j) continue;
if(!used[t])
{
t=-1;
break;
}
}
if(t==-1) continue;
}
used[j]=1;
seq[k]=j;
v2=v+D[seq[k]][seq[k-1]];
dfs(j,k+1,v2);
used[j]=0;
}
}
void main()
{
int i,j;
/*freopen("in.txt","r",stdin);*/
while(scanf("%d %d",&Row,&Column)==2)
{
for(i=0; i<Row; i++) scanf("%s",map[i]);
n=0;
for(i=0; i<Row; i++)
for(j=0; j<Column; j++)
{
if(map[i][j]=='L')
{
Lx=i;
Ly=j;
}
else if(map[i][j]=='#')
{
nut[n].x=i;
nut[n++].y=j;
}
}
nut[n].x=nut[n+1].x=Lx; nut[n].y=nut[n+1].y=Ly;
memset(used,0,sizeof(used));
for(i=0; i<=n; i++)
for(j=i+1; j<=n; j++)
D[i][j]=D[j][i]=distance(nut[i].x,nut[i].y,nut[j].x,nut[j].y);
for(i=0; i<=n; i++)
for(j=i+1; j<=n; j++)
check[i][j]=check[j][i]=checkshort(i,j);
min=Maxint;
seq[0]=n;
dfs(n,1,0);
printf("%d\n",min);
}
}
Posted: Sat Mar 04, 2006 7:51 pm
by trulo17
could someone explain how to implement the dynamic programming solution?
Posted: Fri Mar 10, 2006 8:33 pm
by Larry
Cache the bitmask and where you're at.
Posted: Tue Mar 14, 2006 12:12 pm
by arsalan_mousavian
here is some input , i hope it helps
Code: Select all
20 20
#..................#
....................
....................
....................
....#...............
...............#....
....................
....................
#...........#.......
....................
.........L..........
....................
............#.......
....................
..####..............
....................
...#..........#.....
....................
....................
#..................#
2 2
.L
..
8 8
#......#
.#....#.
..#..#..
...##...
...L....
#..#..#.
.#...#..
..#.#...
and the output is :
I need help :)
Posted: Fri Jun 23, 2006 1:37 pm
by nymo
Hi, I 've tried bfs to make the distance matrix. Then I try backtracking and get TLE. I get correct answer for all test cases of the threads but for some of them, my program takes a lot of time. Can you share your cut off strategy... please, thanks
