1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int Solution::solve(int A, int B, vector<string> &C) {
vector<vector<int>> cost(A,vector<int>(B,INT_MAX));
priority_queue<array<int,3>,vector<array<int,3>>, greater<array<int,3>>> Q;
Q.push({0,0,0});
cost[0][0] = 0;
int dy[4]{-1,0,1,0},dx[4]{0,1,0,-1};
char dc[4] {'U','R','D','L'};
while(!Q.empty()) {
auto [c,y,x] = Q.top(); Q.pop();
if(cost[y][x] != c) continue;
for(int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i], nc = c + (dc[i] != C[y][x]);
if(0 <= ny and ny < A and 0 <= nx and nx < B and cost[ny][nx] > nc) {
cost[ny][nx] = nc;
Q.push({nc,ny,nx});
}
}
}
return cost[A-1][B-1];
}
|
