-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathminimum-moves-to-reach-target-with-rotations.cpp
111 lines (104 loc) · 3.79 KB
/
minimum-moves-to-reach-target-with-rotations.cpp
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
#define dbv(v) cout << #v << "="; for (auto _x : v) cout << _x << ", "; cout << endl
class Solution {
public:
// ??Weekly Contest 156 ????????????????????????????????????????0?
// ??????????
unordered_map<string,int> vis;
int row,col;
int minimumMoves(vector<vector<int>>& grid) {
row=grid.size();
col=grid[0].size();
queue<vector<int>> q;
q.push({0,0,0,1,0});
vis[helper(q.front())]=0;
string target=to_string(row-1)+to_string(col-2)+to_string(row-1)+to_string(col-1);
while(!q.empty()){
auto v=q.front();
q.pop();
auto a=v[0],b=v[1],c=v[2],d=v[3],e=v[4];
if(a==c && b==d-1){ // ??
if(d+1<col && grid[c][d+1]==0){ // ??
auto w=v;
w[1]++;
w[3]++;
w[4]++;
string flag=helper(w);
if(flag==target) return w[4];
if(vis.find(flag)==vis.end() || vis[flag]>w[4]){
vis[flag]=w[4];
q.push(w);
}
}
if(c+1<row && d-1>=0 && grid[c+1][d-1]==0 && a+1<row && b+1<col && grid[a+1][b+1]==0){ // ??
auto w=v;
w[2]++;
w[3]--;
w[4]++;
string flag=helper(w);
if(flag==target) return w[4];
if(vis.find(flag)==vis.end()){
vis[flag]=w[4];
q.push(w);
}
}
if(a+1<row && grid[a+1][b]==0 && grid[c+1][d]==0){ // ????
auto w=v;
w[0]++;
w[2]++;
w[4]++;
string flag=helper(w);
if(flag==target) return w[4];
if(vis.find(flag)==vis.end() || vis[flag]>w[4]){
vis[flag]=w[4];
q.push(w);
}
}
}
else if(a==c-1 && b==d){ // ??
if(c+1<row && grid[c+1][d]==0){ // ??
auto w=v;
w[0]++;
w[2]++;
w[4]++;
string flag=helper(w);
if(flag==target) return w[4];
if(vis.find(flag)==vis.end() || vis[flag]>w[4]){
vis[flag]=w[4];
q.push(w);
}
}
if(c-1>=0 && d+1<col && grid[c-1][d+1]==0 && a+1<row && b+1<col && grid[a+1][b+1]==0){ // ??
auto w=v;
w[2]--;
w[3]++;
w[4]++;
string flag=helper(w);
if(flag==target) return w[4];
if(vis.find(flag)==vis.end() || vis[flag]>w[4]){
vis[flag]=w[4];
q.push(w);
}
}
if(b+1<col && grid[a][b+1]==0 && grid[c][d+1]==0){ // ????
auto w=v;
w[1]++;
w[3]++;
w[4]++;
string flag=helper(w);
if(flag==target) return w[4];
if(vis.find(flag)==vis.end() || vis[flag]>w[4]){
vis[flag]=w[4];
q.push(w);
}
}
}
}
return -1;
}
string helper(vector<int>& vec){
string res="";
for(int i=0;i<4;i++)
res+=to_string(vec[i]);
return res;
}
};