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
|
// 752. Open the Lock
#include "leetcode.h"
/*
* you have a lock in front of you with 4 circular wheels. each wheel has 10
* slots 0-9. the wheels can rotate freely and wrap around. the lock initially
* starts at 0000, a sting representing the state of the 4 wheels. given a list
* of 'deadends', meaning the lock displays any of these codes, the wheels of
* the lock will stop turning and you will be unable to open it. given 'target'
* representing the value of the wheels that will unlock the lock, return the
* minimum total number of turns required to open the lock, or -1 if it is
* impossible
*/
#define SIZE 10000
char queue[SIZE][4] = {0};
int front = -1;
int tail = -1;
int is_empty() { return (tail == front) ? 1 : 0; }
void enqueue(char *wheel) {
front++;
if (front == SIZE)
front = 0;
memcpy(&queue[front][0], wheel, sizeof(char) * 4);
}
char *dequeue() {
if (is_empty() == 1)
return NULL;
tail++;
if (tail == SIZE)
tail = 0;
return &queue[tail][0];
}
int convert_wheels_to_int(char *wheels) {
return (wheels[3] - '0') + (wheels[2] - '0') * 10 + (wheels[1] - '0') * 100 +
(wheels[0] - '0') * 1000;
}
int openLock(char **deadends, int deadendsSIZE, char *target) {
if (!convert_wheels_to_int(target))
return 0;
int visited[SIZE] = {0};
int hop[SIZE] = {0};
int deadends_int;
front = -1;
tail = -1;
for (int d = 0; d < deadendsSIZE; d++) {
deadends_int = convert_wheels_to_int(deadends[d]);
if (!deadends_int)
return -1;
else
visited[deadends_int] = 1;
}
int target_int = convert_wheels_to_int(target);
enqueue("0000");
hop[0] = 0;
visited[0] = 1;
hop[target_int] = -1;
int current_wheel_int;
char *current_wheel;
char neighbour[4];
while (is_empty() != 1) {
if (hop[target_int] != -1)
return hop[target_int];
current_wheel = dequeue();
current_wheel_int = convert_wheels_to_int(current_wheel);
for (int i = 0; i < 4; i++) {
memcpy(&neighbour[0], current_wheel, sizeof(char) * 4);
neighbour[i] = neighbour[i] == '9' ? '0' : neighbour[i] + 1;
if (visited[convert_wheels_to_int(neighbour)] == 0) {
enqueue(neighbour);
hop[convert_wheels_to_int(neighbour)] = hop[current_wheel_int] + 1;
visited[convert_wheels_to_int(neighbour)] = 1;
}
memcpy(&neighbour[0], current_wheel, sizeof(char) * 4);
neighbour[i] = neighbour[i] == '0' ? '9' : neighbour[i] - 1;
if (visited[convert_wheels_to_int(neighbour)] == 0) {
enqueue(neighbour);
hop[convert_wheels_to_int(neighbour)] = hop[current_wheel_int] + 1;
visited[convert_wheels_to_int(neighbour)] = 1;
}
}
}
return hop[target_int];
}
int main() {
char *d1[5][4] = {"0201", "0101", "0102", "1212", "2002"};
char *d2[8][4] = {"8887", "8889", "8878", "8898",
"8788", "8988", "7888", "9888"};
char *t1 = "0202", *t2 = "8888";
printf("%d\n", openLock((char **)d1, 5, t1)); // expect: 6
printf("%d\n", openLock((char **)d2, 8, t2)); // expect: -1
}
|