838 - Worm World

Moderator: Board moderators

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

838 - Worm World

I try to solve this problem, but I can't figure out a method other than a brute force dfs.
Can somebody give me some hints?
Thanks a lot!

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Hi.
I don't know how to solve this problem unless using DFS.
But, my program gives Runtime Error.
Could anyone tell me why?
[c]
#include<stdio.h>

struct node{
int row;
int col;
int depth;
int map[12][12];
char visited;
};

int choose(struct node node[],int *n_nodes);
void expand(struct node node[],int chosen,int *n_nodes,int size,int *solution);
void update_map(int map[12][12],int size,int number);
void copy_map(int map_1[12][12],int map_2[12][12],int size);

main()
{
struct node node[150];
int cases,i,j,m,k,size,map[12][12],n_nodes,chosen,solution;
scanf("%d",&cases);
for(i=0;i<cases;i++)
{
scanf("%d",&size);
for(j=0;j<size;j++)
for(k=0;k<size;k++)
scanf("%d",&map[j][k]);

solution=0;
for(m=0;m<size;m++)
{
for(k=0;k<size;k++)
{
node[0].row=m;
node[0].col=k;
node[0].depth=1;
node[0].visited=0;
n_nodes=1;
copy_map(node[0].map,map,size);
update_map(node[0].map,size,map[m][k]);

while(1)
{
chosen=choose(node,&n_nodes);
if(chosen==-1)
break;
expand(node,chosen,&n_nodes,size,&solution);
}
}
}
printf("%d\n",solution);
if(i!=cases-1)
printf("\n");
}
}

int choose(struct node node[],int *n_nodes)
{
int i;
for(i=*n_nodes-1;i>=0;i--)
if(node.visited==0)
return(i);
else
*n_nodes--;
return(-1);
}

void expand(struct node node[],int chosen,int *n_nodes,int size,int *solution)
{
int i,n_expandidos,row,col;
node[chosen].visited=1;
n_expandidos=0;
row=node[chosen].row;
col=node[chosen].col;
if(row-1>=0)
if(node[chosen].map[row-1][col]!=-1)
{
node[*n_nodes].row=row-1;
node[*n_nodes].col=col;
node[*n_nodes].depth=node[chosen].depth+1;
node[*n_nodes].visited=0;
copy_map(node[*n_nodes].map,node[chosen].map,size);
update_map(node[*n_nodes].map,size,node[chosen].map[row-1][col]);
(*n_nodes)++;
n_expandidos++;
}
if(row+1<size)
if(node[chosen].map[row+1][col]!=-1)
{
node[*n_nodes].row=row+1;
node[*n_nodes].col=col;
node[*n_nodes].depth=node[chosen].depth+1;
node[*n_nodes].visited=0;
copy_map(node[*n_nodes].map,node[chosen].map,size);
update_map(node[*n_nodes].map,size,node[chosen].map[row+1][col]);
(*n_nodes)++;
n_expandidos++;
}
if(col-1>=0)
if(node[chosen].map[row][col-1]!=-1)
{
node[*n_nodes].row=row;
node[*n_nodes].col=col-1;
node[*n_nodes].depth=node[chosen].depth+1;
node[*n_nodes].visited=0;
copy_map(node[*n_nodes].map,node[chosen].map,size);
update_map(node[*n_nodes].map,size,node[chosen].map[row][col-1]);
(*n_nodes)++;
n_expandidos++;
}
if(col+1<size)
if(node[chosen].map[row][col+1]!=-1)
{
node[*n_nodes].row=row;
node[*n_nodes].col=col+1;
node[*n_nodes].depth=node[chosen].depth+1;
node[*n_nodes].visited=0;
copy_map(node[*n_nodes].map,node[chosen].map,size);
update_map(node[*n_nodes].map,size,node[chosen].map[row][col+1]);
(*n_nodes)++;
n_expandidos++;
}
if(n_expandidos==0)
if(*solution<node[chosen].depth)
*solution=node[chosen].depth;
return;
}

void update_map(int map[12][12],int size,int number)
{
int i,j;
for(i=0;i<size;i++)
for(j=0;j<size;j++)
if(map[j]==number)
map[j]=-1;
return;
}

void copy_map(int map_1[12][12],int map_2[12][12],int size)
{
int i,j;
for(i=0;i<size;i++)
for(j=0;j<size;j++)
map_1[j]=map_2[j];
return;
}

[/c]

brianschroeder
New poster
Posts: 2
Joined: Thu Oct 24, 2002 8:24 am
henar, the bug in your program is in your choose function where you have *n_nodes--; it should be (*n_nodes)--;

But now your program has the same problem as mine: it is too slow to pass the judging. There must be a better algorithm, but does anyone know what it is?

-Brian Schroeder

MV
New poster
Posts: 4
Joined: Thu Oct 31, 2002 11:30 am

Speed Up

A good thing to do is to determine the absolute maximum value of the answer before doing the DFS, and then quit searching if the maxvalue has been found. Helps a lot with a simple 0.144 grid.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
I am doing a dfs with some heuristics, like early exit, but it is still too slow

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
I have tried to memorize some calculations, i.e. all the warms from point P1 and to use it while calculating a warm from P2 to P3 through P1. It was enough to get AC. With 7628 K memory

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

WHY???

when I solved ths problem I submited for about 15 times and I got just TLE but when I changed my sequence of backtrack (with hint from Haamed Gheibi )from DOWN UP LEFT RIGHT to DOWN RIGHT UP LEFT i got Accepted just in 0.006 sec!!!
this is so strange!!!

[/cpp]

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Internet links ? Good Algorithm ?

Denisjuk,
Can you be more detailed about the algorithm you use.
( only if you like to ! )

1) is it backtracking ( I guess so )