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
| class Solution {
typedef pair<int, int> block_t;
typedef pair<block_t, block_t> block2_t;
typedef pair<block2_t, int> state_t; // step
public:
int minimumMoves(vector<vector<int>>& grid) {
int N = grid.size();
queue<state_t> q;
q.push({{{0, 0}, {0, 1}}, 0});
set<block2_t> visited;
visited.insert({{0, 0}, {0, 1}});
pair<set<block2_t>::iterator, bool> rst;
while (!q.empty()) {
state_t s = q.front(); q.pop();
block_t a = s.first.first;
block_t b = s.first.second;
int step = s.second;
if (a.first == b.first) {
// horizontal
if (a.first == N-1 && a.second == N-2 && b.first == N-1 && b.second == N-1) {
return step;
}
if (b.second+1 < N && grid[b.first][b.second+1] == 0){
// right
rst = visited.insert({{b.first, b.second}, {b.first, b.second+1}});
if (rst.second) {
q.push({{{b.first, b.second}, {b.first, b.second+1}}, step+1});
}
}
if (a.first+1 < N && grid[a.first+1][a.second] == 0 && grid[b.first+1][b.second] == 0) {
// down
rst = visited.insert({{a.first+1, a.second}, {b.first+1, b.second}});
if (rst.second) {
q.push({{{a.first+1, a.second}, {b.first+1, b.second}}, step+1});
}
// clockwise
rst = visited.insert({{a.first, a.second}, {a.first+1, a.second}});
if (rst.second) {
q.push({{{a.first, a.second}, {a.first+1, a.second}}, step+1});
}
}
} else {
// vertical
if (b.first+1 < N && grid[b.first+1][b.second] == 0){
// down
rst = visited.insert({{b.first, b.second}, {b.first+1, b.second}});
if (rst.second) {
q.push({{{b.first, b.second}, {b.first+1, b.second}}, step+1});
}
}
if (a.second+1 < N && grid[a.first][a.second+1] == 0 && grid[b.first][b.second+1] == 0) {
// right
rst = visited.insert({{a.first, a.second+1}, {b.first, b.second+1}});
if (rst.second) {
q.push({{{a.first, a.second+1}, {b.first, b.second+1}}, step+1});
}
// anti-clockwise
rst = visited.insert({{a.first, a.second}, {a.first, a.second+1}});
if (rst.second) {
q.push({{{a.first, a.second}, {a.first, a.second+1}}, step+1});
}
}
}
}
return -1;
}
};
|