# Leetcode 499 Solution

https://leetcode.com/problems/the-maze-iii

## Solution

``````class Solution {
public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
int m = maze.size();
int n = maze[0].size();
vector<vector<int>> dists(m, vector<int>(n, INT_MAX));
vector<vector<string>> actions(m, vector<string>(n));

queue<pair<int, int>> q;
dists[ball[0]][ball[1]] = 0;
q.push(make_pair(ball[0], ball[1]));

auto dest = make_pair(hole[0], hole[1]);
while (q.empty() == false)
{
auto pt = q.front();
auto y = pt.first;
auto x = pt.second;
q.pop();

int dy[4] = {0, 0, -1, 1};
int dx[4] = {-1, 1, 0, 0};
char action_ch[4] = {'l', 'r', 'u', 'd'};

for (int t = 0; t < 4; t++)
{
int i = y;
int j = x;

int step = 0;
while (i + dy[t] >= 0 && i + dy[t] < m && j + dx[t] >= 0 && j + dx[t] < n && maze[i + dy[t]][j + dx[t]] == 0)
{
i += dy[t];
j += dx[t];
step++;

if (i == hole[0] && j == hole[1])
break;
}

auto pt = make_pair(i, j);
auto next_dist = dists[y][x] + step;
string action = actions[y][x] + action_ch[t];

if (dists[i][j] > next_dist)
{
q.push(pt);
dists[i][j] = next_dist;
actions[i][j] = action;
}
else if (dists[i][j] == next_dist && action < actions[i][j])
{
q.push(pt);
actions[i][j] = action;
}
}
}

if (dists[dest.first][dest.second] == INT_MAX)
return "impossible";
else
return actions[dest.first][dest.second];
}
};
``````