UVa 314 - Robot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int block_maps[55][55];
int point_maps[55][55];
int moves_maps[55][55][4];
int dxy[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int get_direct(char str[])
{
	if (!strcmp(str, "north")) {
		return 0;
	}else if (!strcmp(str, "east")) {
		return 1;
	}else if (!strcmp(str, "south")) {
		return 2;
	}else if (!strcmp(str, "west")) {
		return 3;
	}else return -1;
}

int queue_x[11111];
int queue_y[11111];
int queue_d[11111];
int bfs(int N, int M, int Sx, int Sy, int Sd, int Ex, int Ey)
{
	memset(moves_maps, 0, sizeof(moves_maps));
	moves_maps[Sx][Sy][Sd] = 1;
	queue_x[0] = Sx;
	queue_y[0] = Sy;
	queue_d[0] = Sd;
	int head = 0, tail = 1;
	while (head < tail) {
		int x = queue_x[head];
		int y = queue_y[head];
		int d = queue_d[head];
		if (x == Ex && y == Ey) {
			return moves_maps[x][y][d]-1;
		}
		// move 
		for (int s = 1; s <= 3; ++ s) {
			int new_x = x + dxy[d][0]*s;
			int new_y = y + dxy[d][1]*s;
			if (new_x > 0 && new_x < N && new_y > 0 && new_y < M) {
				int flag = 0;
				for (int t = 1; t <= s; ++ t) {
					if (point_maps[x + dxy[d][0]*t][y + dxy[d][1]*t]) {
						flag = 1;
					}
				}
				if (!moves_maps[new_x][new_y][d] && !flag) {
					moves_maps[new_x][new_y][d] = moves_maps[x][y][d]+1;
					queue_x[tail] = new_x;
					queue_y[tail] = new_y;
					queue_d[tail] = d;			
					tail ++;
				}
			}
		}
		// turn left
		if (!moves_maps[x][y][(d+3)%4]) {
			moves_maps[x][y][(d+3)%4] = moves_maps[x][y][d]+1;
			queue_x[tail] = x;
			queue_y[tail] = y;
			queue_d[tail] = (d+3)%4;
			tail ++;
		}
		// turn right
		if (!moves_maps[x][y][(d+1)%4]) {
			moves_maps[x][y][(d+1)%4] = moves_maps[x][y][d]+1;
			queue_x[tail] = x;
			queue_y[tail] = y;
			queue_d[tail] = (d+1)%4;
			tail ++;
		}
		head ++;
	}
	return -1;
}

int main()
{
	int  N, M, Br, Bc, Er, Ec;
	char direct[10];
	while (~scanf("%d%d",&N,&M) && N+M) {
		for (int i = 0; i < N; ++ i) {
			for (int j = 0; j < M; ++ j) {
				scanf("%d",&block_maps[i][j]);
			}
		}
		scanf("%d%d%d%d%s",&Br,&Bc,&Er,&Ec,direct);
		
		memset(point_maps, 0 , sizeof(point_maps));
		for (int i = 0; i < N; ++ i) {
			for (int j = 0; j < M; ++ j) {
				if (block_maps[i][j]) {
					point_maps[i+0][j+0] = 1;
					point_maps[i+0][j+1] = 1;
					point_maps[i+1][j+0] = 1;
					point_maps[i+1][j+1] = 1;
				}
			}
		}

		printf("%dn",bfs(N, M, Br, Bc, get_direct(direct), Er, Ec));
	}
	
	return 0;
}