// The Maze #define FOR(i, a, b) for (remove_cv::type>::type i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) class Solution { public: string findShortestWay(vector>& maze, vector& ball, vector& hole) { const int dx[] = {1,0,0,-1}, dy[] = {0,-1,1,0}; int m = maze.size(), n = maze[0].size(); vector> d(m, vector(n, INT_MAX)); vector> p(m, vector(n)); vector> v(m, vector(n, 0)); d[ball[0]][ball[1]] = 0; for(;;) { int mind = INT_MAX, x0 = -1, y0 = -1; REP(i, m) REP(j, n) if (d[i][j] < mind && !v[i][j]) mind = d[i][j], x0 = i, y0 = j; if (x0 < 0) return "impossible"; if (x0 == hole[0] && y0 == hole[1]) return p[x0][y0]; v[x0][y0] = 1; REP(i, 4) { int x = x0, y = y0, x1, y1, l = 0; for(;;) { x1 = x+dx[i]; y1 = y+dy[i]; char ok = 1; if (x1 == hole[0] && y1 == hole[1]) { ok = 0; x = x1; y = y1; l++; } if (! (ok && unsigned(x1) < m && unsigned(y1) < n && ! maze[x1][y1])) { if (mind+l < d[x][y]) { d[x][y] = mind+l; p[x][y] = "z"; } if (mind+l == d[x][y]) p[x][y] = min(p[x][y], p[x0][y0]+"dlru"[i]); break; } x = x1; y = y1; l++; } } } } };