fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <unordered_set>
  7. #include <unordered_map>
  8. #include <stack>
  9. #include <queue>
  10. #include <functional>
  11. #include <algorithm>
  12. using namespace std;
  13.  
  14. class Motion {
  15. public: 
  16.    pair<int, int> pos;
  17.    string path; 
  18.    Motion(pair<int, int> p_, string s_) : pos(p_), path(s_) {}
  19. };
  20. class Solution {
  21. public:
  22.     /**
  23.      * @param maze: the maze
  24.      * @param ball: the ball position
  25.      * @param hole: the hole position
  26.      * @return: the lexicographically smallest way
  27.      */
  28.     string findShortestWay(vector<vector<int>> &maze, vector<int> &ball, vector<int> &hole) {
  29.         // write your code here
  30.         int i, j, k, l, n = maze.size(), m = maze[0].size(), x, y, nx, ny, len = 0, level = 0;
  31.  
  32.         queue<Motion> que; 
  33.         que.push(Motion({ball[0], ball[1]}, "")); 
  34.  
  35.         bool found = false;
  36.         string path;
  37.         vector<string> res;
  38.         int flag[n][m];
  39.         fill_n(&flag[0][0], n*m, 0);
  40.         int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
  41.         string dirs = "udlr";
  42.  
  43.         while(!que.empty()) {
  44.             len = que.size();
  45.             for(l = 0; l < len; l++) {
  46.                 auto& node = que.front();
  47.                 x = node.pos.first;
  48.                 y = node.pos.second;
  49.                 path = node.path;
  50.                 que.pop();
  51.                 if(!path.empty()) {
  52.                    k = dirs.find(path.back());
  53.                    flag[x][y] |= (1<<k);
  54.                 }
  55.  
  56.                 if(x == hole[0] && y == hole[1]) {
  57.                     res.push_back(path); 
  58.                     found = true;
  59.                 } else {
  60.                     nx = x; ny = y;
  61.                     cout<<"("<<nx<<","<<ny<<")"<<"to "<<path.back()<<endl;
  62.                     getNext(nx, ny, path);
  63.                     // Hit the wall Change direction
  64.                     if(path.empty() || !isValid(nx, ny, n, m) || maze[nx][ny]==1) {
  65.                         for(k=0; k<4; k++) {
  66.                             nx = x + dx[k]; ny = y + dy[k];
  67.                             if(isValid(nx, ny, n, m) && maze[nx][ny]==0 && !(flag[nx][ny]&(1<<k))) {
  68.  
  69.                                 que.push(Motion({nx, ny}, path+dirs[k]));
  70.                                 cout<<"Transfer to "<<path+dirs[k]<<endl;
  71.                             }
  72.                         }
  73.                     } else {
  74.                     	k = dirs.find(path.back());
  75.                         if(maze[nx][ny]==0 && !(flag[nx][ny]&(1<<k))) {
  76.                             que.push(Motion({nx, ny}, path));
  77.                         }
  78.                     }
  79.  
  80.                 }
  81.             }
  82.             level++;
  83.             if(found) {
  84.                cout<<"The minimum step: "<<level<<endl;
  85.                break;
  86.             } 
  87.         }
  88.  
  89.         if(!found) return "impossible";
  90.         cout<<"All solution: "<<endl;
  91.         for(auto& str : res) {
  92.         	cout<<str<<", ";
  93.         }
  94.         cout<<endl;
  95.         path = res[0];
  96.         for(i = 1; i < res.size(); i++) {
  97.             if(path.compare(res[i]) > 0) {
  98.                 path = res[i];
  99.             }
  100.         }
  101.  
  102.         return path;
  103.     }
  104.  
  105.     bool isValid(int x, int y, int n, int m) {
  106.         return x>=0 && x<n && y >=0 && y<m;
  107.     }
  108.  
  109.     void getNext(int& x, int& y, string& path) {
  110.         if(path.empty()) return;
  111.         char& dir = path.back();
  112.         if(dir=='u') --x; 
  113.         else if(dir=='d') ++x;
  114.         else if(dir=='l') --y;
  115.         else ++y;
  116.     }
  117. };
  118.  
  119. int main() {
  120.  
  121.    Solution solve;
  122.    vector<vector<int>> input = {{0,0,0,0,0},{1,1,0,0,1},{0,0,0,0,0},{0,1,0,0,1},{0,1,0,0,0}};
  123.    vector<int> ball = {4,3}, hole = {0,1};
  124.    string ret = solve.findShortestWay(input, ball, hole);
  125.  
  126.    cout<<"Result: "<<ret<<endl;
  127.    return 0;
  128. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(4,3)to 
Transfer to u
Transfer to l
Transfer to r
(3,3)to u
(4,2)to l
Transfer to lu
Transfer to lr
(4,4)to r
Transfer to rl
(2,3)to u
(3,2)to u
(4,3)to r
(4,3)to l
(1,3)to u
(2,2)to u
(0,3)to u
Transfer to ud
Transfer to ul
Transfer to ur
(1,2)to u
(1,3)to d
(0,2)to l
(0,4)to r
Transfer to url
(0,2)to u
Transfer to lud
Transfer to lul
Transfer to lur
(2,3)to d
(0,3)to l
(1,2)to d
(0,3)to r
The minimum step: 7
All solution: 
ul, lul, 
Result: lul
https://ideone.com/xgrA9I
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!