10021 - Cube in the labirint

[Adrian Kuegel]

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]

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]

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]

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.
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! )

[Amir Aavani]

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]

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...

[angga888]

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.


Anggakusuma

[skylander]

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]

[angga888]

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]

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

[matrix2]

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?

[jambon_vn]

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]

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 */
}

[jambon_vn]

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

[matrix2]

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.