OJ Board

Code: Select all

10 3
1 1
5 2
v
4 2
5 2
h
5 2
5 1

Code: Select all

1

3 2
1 1
2 2

Code: Select all

6

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