10021 - Cube in the labirint

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

10021 - Cube in the labirint

Post by Adrian Kuegel » Fri Feb 15, 2002 10:22 pm

I don't know why I am always getting Wrong Answer. I tested my program with many inputs, including some with end point or start point outside the board, and the values seemed to be ok. Perhaps someone knows a tricky input, that I have not considered? Is there any difficult input format (blank lines etc.)?

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Sat Feb 16, 2002 2:03 pm

I had no problems with the input or special cases as far as i recall.
Did you consider that the cube only has to end with the same side up, i.e it is allowed to have been rotated ?

Kristoffer Hansen

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Feb 17, 2002 12:19 am

Yes, I did so. But I made a stupid mistake and had used <= instead of < when testing if a point is inside the labirint or not.

<font size=-1>[ This Message was edited by: Adrian Kuegel on 2002-02-16 23:25 ]</font>

seKallePuk
New poster
Posts: 2
Joined: Mon Mar 01, 2004 11:08 am

10021-Cube in labirint WA!

Post by seKallePuk » Mon Mar 01, 2004 11:19 am

I don't know why but it doesn't matter how hard you try!
I got WA for countless times, but I really don't know why. :cry: :(
It's clear this is a simple BFS. I test many samples but It seems It's O.K.
may someone help with some special testcases!!!

(you can count on me for your next dinner! :lol: )

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani » Tue Apr 06, 2004 8:28 am

Dear Adrian Kuegel
I think I solve the problem correctly but getting WA.
I want to know what is the lower point of the board. is it (0, 0) or (1, 1) or no limit?
thnx

skylander
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:

10021 - Cube in Labirint

Post by skylander » Wed Jun 02, 2004 10:32 am

i attempted to do this problem using a depth first traversal, but it seems to be to inefficient to solve the problem within 10s.... and looking at the timings achieved by those who solved the problem, mostly below one fifths of a sec...so there should be another more efficient approach to this problem.....wonder if those who has their solution accepted could provide us with some tips and suggestions.....thx...:)

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Wed Jun 02, 2004 12:04 pm

i attempted to do this problem using a depth first traversal, but it seems to be to inefficient to solve the problem within 10s.... and looking at the timings achieved by those who solved the problem, mostly below one fifths of a sec...so there should be another more efficient approach to this problem.....
I solved this problem using BFS.

Hope it helps. :wink:


Anggakusuma

skylander
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:

Post by skylander » Wed Jun 02, 2004 1:51 pm

thx for your suggestion....i have modified the code to use breadth first search...and tried my program with test data that i can think of...somehow the judge gives a WA....can anyone take a look at my code and see what i have overlooked or misunderstood....thanks....

[c]
code accepted..:)
[/c]
Last edited by skylander on Thu Jun 03, 2004 4:50 am, edited 1 time in total.

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Wed Jun 02, 2004 7:44 pm

I think your program have some problems dealing with the wall.

Consider this case:

Code: Select all

10 3
1 1
5 2
v
4 2
5 2
h
5 2
5 1
The target coordinate is completely surrounded by walls, so the answer should be "No solution".


Anggakusuma

skylander
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:

Post by skylander » Thu Jun 03, 2004 4:49 am

i seem to have confused the locations of the walls....so careless of me...now its an AC....thanks Anggakusuma..:)

matrix2
New poster
Posts: 19
Joined: Wed Jul 21, 2004 11:14 am
Location: Suceava, Romania
Contact:

10021 - How to solve?

Post by matrix2 » Wed Oct 06, 2004 11:20 pm

How can I solve this problem?
I've tried DFS first, then BFS, but WA. It seems a cell can be visited more than once. So it would go for TLE, in't it?
Things are simple, but we make them complex.

jambon_vn
New poster
Posts: 15
Joined: Wed Sep 29, 2004 6:03 am

Post by jambon_vn » Thu Oct 07, 2004 7:06 am

The problem do not say the cell can be repeated or not. But to find the minimal number of moves, it is wise when each cell will be visited no more once.

I think BFS or DFS will work in this problem. If you stil have WA, please post your code. Maybe someone can point out your mistake.

matrix2
New poster
Posts: 19
Joined: Wed Jul 21, 2004 11:14 am
Location: Suceava, Romania
Contact:

Post by matrix2 » Thu Oct 07, 2004 9:02 am

I think that a cell can be repeated. So the input:

Code: Select all

1

3 2
1 1
2 2

may give an answer like that:

Code: Select all

6

otherwise "No solution".
But if I do a DF traversal then I'll get TLE.

Here is my DFS code:

Code: Select all

#include <stdio.h>
#include <memory.h>


/* die faces */
#define UP    0
#define DOWN  1
#define LEFT  2
#define RIGHT 3
#define FRONT 4
#define BACK  5


int lin, col;/* number fo lines and columns */
int sx, sy; /* start x y */
int fx, fy; /* stop (finish) x y */
char walls[10][10][10][10]; /* walls[line1][col1][line2][col2] = 1 => it is a wall */
char viz[10][10]; /* retain traversed cells */


int DFS(int x, int y, int die_face, int num_moves);
int change_die_face(int die_face, int a, int b, int after_a, int after_b);


int main(void)
{
	char buf[80]; 
	int tst;    
	int tx, ty; /* temporary x y */
	int vert; 
	int tmp;


	gets(buf);
	sscanf(buf, "%d", &tst);
	gets(buf);

	while(tst--)
	{
		gets(buf);
		sscanf(buf, "%d%d", &lin, &col);
		
		gets(buf);
		sscanf(buf, "%d%d", &sx, &sy);
		sx--;
		sy--;

		gets(buf);
		sscanf(buf, "%d%d", &fx, &fy);
		fx--;
		fy--;

		vert = 0;
		memset(walls, 0, 10000);
		memset(viz, 0, 100);

		while(gets(buf) != NULL)
		{
			if(buf[0] == 0)
				break;
			else if(buf[0] == 'v')
				vert = 1;
			else if(buf[0] == 'h')
				vert = 0;
			else
			{
				sscanf(buf, "%d%d", &tx, &ty);
				tx--;
				ty--;
				if( vert ) 
					walls[tx][ty][tx+1][ty] = walls[tx+1][ty][tx][ty] = 1;
				else
					walls[tx][ty][tx][ty+1] = walls[tx][ty+1][tx][ty] = 1;
			}
		}
		
		tmp = DFS(sx, sy, DOWN, 0);
		if(tmp >= 0)
			printf("%d\n", tmp);
		else
			printf("No solution\n");

		if(tst) 
			printf("\n");
	}

	return 0;
}


int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};

int DFS(int x, int y, int die_face, int num_moves)
{
	if(x == fx && y == fy && die_face == DOWN)
		return num_moves;
	else
	{
		int a, b, t, i, min = -1;

		viz[x][y]++;

		for(i = 0; i < 4; i++)
		{
			a = x + dx[i];
			b = y + dy[i];
			if(0 <= a && a < lin && 0 <= b && b < col)
				if(viz[a][b] < 1 && walls[x][y][a][b] == 0) /* viz[a][b] < 2 (??? => TLE) */
					if( (t = DFS(a, b, change_die_face(die_face, x, y, a, b), num_moves+1)) > 0)
						if(min == -1)
							min = t;
						else if(t < min)
							min = t;
		}

		viz[x][y]--;

		return min;
	}
}

int change_die_face(int die_face, int a, int b, int after_a, int after_b)
{
	if(after_a == a-1 && after_b == b)
		switch(die_face)
		{
		case UP:	return FRONT;	
		case DOWN:	return BACK;
		case LEFT:	return LEFT;
		case RIGHT:	return RIGHT;
		case FRONT:	return DOWN;
		case BACK:	return UP;
		}
	else if(after_a == a+1 && after_b == b)
		switch(die_face)
		{
		case UP:	return BACK;
		case DOWN:	return FRONT;
		case LEFT:	return LEFT;
		case RIGHT:	return RIGHT;
		case FRONT:	return UP;
		case BACK:	return DOWN;
		}
	else if(after_a == a && after_b == b+1)
		switch(die_face)
		{
		case UP:	return RIGHT;
		case DOWN:	return LEFT;
		case LEFT:	return UP;
		case RIGHT:	return DOWN;
		case FRONT:	return FRONT;
		case BACK:	return BACK;
		}
	else if(after_a == a && after_b == b-1)
		switch(die_face)
		{
		case UP:	return LEFT;
		case DOWN:	return RIGHT;
		case LEFT:	return DOWN;
		case RIGHT:	return UP;
		case FRONT:	return FRONT;
		case BACK:	return BACK;
		}
	return -1; /* otherwise */
}
Things are simple, but we make them complex.

jambon_vn
New poster
Posts: 15
Joined: Wed Sep 29, 2004 6:03 am

Post by jambon_vn » Thu Oct 07, 2004 3:04 pm

I did not see your code but actually I misunderstand this problem. You are right about repeated cell. Cell can be repeated.

matrix2
New poster
Posts: 19
Joined: Wed Jul 21, 2004 11:14 am
Location: Suceava, Romania
Contact:

Post by matrix2 » Thu Oct 07, 2004 3:24 pm

Yeeeess...I've solved it. And lastly got AC. 4 ms and 420 k memory.

Some explanations:
- a cell can be repeated more than once
- it is preferably to use a BFS (Bradth First Search) in Labirint: that means you must search in all four directions simultaneously to get to final destination in small amount of time. DFS (Depth First Search -something like Backtracking) gave me a head ache because didn't finish to run!!! ==> TLE.
- for each search from a cell1 to a cell2 and then to a cell3 (like cell1->cell2->cell3) we must not turn back. I mean you musn't go from cell3 go to cell2, but it is right to go from cell3->cell4-> and then to cell1. In this case cell1 is visited twice in this chain of cells (cell1->cell2->cell3->cell4->cell1) and we should not repeat this cell after this.
- I used a queue for BFS
Good luck.

P.S. I've solved this even with Java, but I've got CE because it seems like Online Judge Java compiler doesn't know about class Vector. So, I recommend you C, or C++ for solving this problem.
Things are simple, but we make them complex.

Post Reply

Return to “Volume 100 (10000-10099)”