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
|
// 1138. Alphabet Board Path
#include <stdio.h>
#include <stdlib.h>
/*
* on an alphabet board, we start position [0,0], corresponding to character
* 'board[0][0]'. here, 'board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy",
* "z"]' as show in the diagram (see page). return a sequence of moves that
* makes our answer equal to 'target' in the minimum numbe of moves. (in any
* order/path)
*/
char *alphabetBoardPath(char *target) {
char map[26][2] = {0};
int i;
for (i = 0; i < 26; i++) {
map[i][0] = i % 5;
map[i][1] = i / 5;
}
char *curr, *prev;
curr = "a";
prev = target;
char *ans = (char *)malloc(100 * sizeof(char));
int ans_size = 100;
i = 0;
while (*prev) {
if (ans_size - i < 11) {
ans_size += 11;
char *new_ans = (char *)realloc(ans, ans_size * sizeof(char));
if (new_ans)
ans = new_ans;
}
int j = (int)(*prev) - (int)('a');
int k = (int)(*curr) - (int)('a');
int dx = map[j][0] - map[k][0];
int dy = map[j][1] - map[k][1];
if (dx < 0)
while (dx) {
ans[i++] = 'L';
dx++;
}
if (dy > 0)
while (dy) {
ans[i++] = 'D';
dy--;
}
if (dy < 0)
while (dy) {
ans[i++] = 'U';
dy++;
}
if (dx > 0)
while (dx) {
ans[i++] = 'R';
dx--;
}
ans[i++] = '!';
curr = prev;
prev++;
}
ans[i] = '\0';
return ans;
}
int main() {
char *t1 = "leet";
char *t2 = "code";
printf("%s\n", alphabetBoardPath(t1)); // expect: DDR!UURRR!!DDD!
printf("%s\n", alphabetBoardPath(t2)); // expect: RR!DDRR!UUL!R!
}
|