#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;
class Motion {
public:
pair<int, int> pos;
string path;
Motion(pair<int, int> p_, string s_) : pos(p_), path(s_) {}
};
class Solution {
public:
/**
* @param maze: the maze
* @param ball: the ball position
* @param hole: the hole position
* @return: the lexicographically smallest way
*/
string findShortestWay(vector<vector<int>> &maze, vector<int> &ball, vector<int> &hole) {
// write your code here
int i, j, k, l, n = maze.size(), m = maze[0].size(), x, y, nx, ny, len = 0, level = 0;
queue<Motion> que;
que.push(Motion({ball[0], ball[1]}, ""));
bool found = false;
string path;
vector<string> res;
int flag[n][m];
fill_n(&flag[0][0], n*m, 0);
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string dirs = "udlr";
while(!que.empty()) {
len = que.size();
for(l = 0; l < len; l++) {
auto& node = que.front();
x = node.pos.first;
y = node.pos.second;
path = node.path;
que.pop();
if(!path.empty()) {
k = dirs.find(path.back());
flag[x][y] |= (1<<k);
}
if(x == hole[0] && y == hole[1]) {
res.push_back(path);
found = true;
} else {
nx = x; ny = y;
cout<<"("<<nx<<","<<ny<<")"<<"to "<<path.back()<<endl;
getNext(nx, ny, path);
// Hit the wall Change direction
if(path.empty() || !isValid(nx, ny, n, m) || maze[nx][ny]==1) {
for(k=0; k<4; k++) {
nx = x + dx[k]; ny = y + dy[k];
if(isValid(nx, ny, n, m) && maze[nx][ny]==0 && !(flag[nx][ny]&(1<<k))) {
que.push(Motion({nx, ny}, path+dirs[k]));
cout<<"Transfer to "<<path+dirs[k]<<endl;
}
}
} else {
k = dirs.find(path.back());
if(maze[nx][ny]==0 && !(flag[nx][ny]&(1<<k))) {
que.push(Motion({nx, ny}, path));
}
}
}
}
level++;
if(found) {
cout<<"The minimum step: "<<level<<endl;
break;
}
}
if(!found) return "impossible";
cout<<"All solution: "<<endl;
for(auto& str : res) {
cout<<str<<", ";
}
cout<<endl;
path = res[0];
for(i = 1; i < res.size(); i++) {
if(path.compare(res[i]) > 0) {
path = res[i];
}
}
return path;
}
bool isValid(int x, int y, int n, int m) {
return x>=0 && x<n && y >=0 && y<m;
}
void getNext(int& x, int& y, string& path) {
if(path.empty()) return;
char& dir = path.back();
if(dir=='u') --x;
else if(dir=='d') ++x;
else if(dir=='l') --y;
else ++y;
}
};
int main() {
Solution solve;
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}};
vector<int> ball = {4,3}, hole = {0,1};
string ret = solve.findShortestWay(input, ball, hole);
cout<<"Result: "<<ret<<endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8dW5vcmRlcmVkX3NldD4KI2luY2x1ZGUgPHVub3JkZXJlZF9tYXA+CiNpbmNsdWRlIDxzdGFjaz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNsYXNzIE1vdGlvbiB7CnB1YmxpYzogCiAgIHBhaXI8aW50LCBpbnQ+IHBvczsKICAgc3RyaW5nIHBhdGg7IAogICBNb3Rpb24ocGFpcjxpbnQsIGludD4gcF8sIHN0cmluZyBzXykgOiBwb3MocF8pLCBwYXRoKHNfKSB7fQp9OwpjbGFzcyBTb2x1dGlvbiB7CnB1YmxpYzoKICAgIC8qKgogICAgICogQHBhcmFtIG1hemU6IHRoZSBtYXplCiAgICAgKiBAcGFyYW0gYmFsbDogdGhlIGJhbGwgcG9zaXRpb24KICAgICAqIEBwYXJhbSBob2xlOiB0aGUgaG9sZSBwb3NpdGlvbgogICAgICogQHJldHVybjogdGhlIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXN0IHdheQogICAgICovCiAgICBzdHJpbmcgZmluZFNob3J0ZXN0V2F5KHZlY3Rvcjx2ZWN0b3I8aW50Pj4gJm1hemUsIHZlY3RvcjxpbnQ+ICZiYWxsLCB2ZWN0b3I8aW50PiAmaG9sZSkgewogICAgICAgIC8vIHdyaXRlIHlvdXIgY29kZSBoZXJlCiAgICAgICAgaW50IGksIGosIGssIGwsIG4gPSBtYXplLnNpemUoKSwgbSA9IG1hemVbMF0uc2l6ZSgpLCB4LCB5LCBueCwgbnksIGxlbiA9IDAsIGxldmVsID0gMDsKICAgICAgICAKICAgICAgICBxdWV1ZTxNb3Rpb24+IHF1ZTsgCiAgICAgICAgcXVlLnB1c2goTW90aW9uKHtiYWxsWzBdLCBiYWxsWzFdfSwgIiIpKTsgCiAgICAgICAgCiAgICAgICAgYm9vbCBmb3VuZCA9IGZhbHNlOwogICAgICAgIHN0cmluZyBwYXRoOwogICAgICAgIHZlY3RvcjxzdHJpbmc+IHJlczsKICAgICAgICBpbnQgZmxhZ1tuXVttXTsKICAgICAgICBmaWxsX24oJmZsYWdbMF1bMF0sIG4qbSwgMCk7CiAgICAgICAgaW50IGR4W10gPSB7LTEsIDEsIDAsIDB9LCBkeVtdID0gezAsIDAsIC0xLCAxfTsKICAgICAgICBzdHJpbmcgZGlycyA9ICJ1ZGxyIjsKICAgICAgICAKICAgICAgICB3aGlsZSghcXVlLmVtcHR5KCkpIHsKICAgICAgICAgICAgbGVuID0gcXVlLnNpemUoKTsKICAgICAgICAgICAgZm9yKGwgPSAwOyBsIDwgbGVuOyBsKyspIHsKICAgICAgICAgICAgICAgIGF1dG8mIG5vZGUgPSBxdWUuZnJvbnQoKTsKICAgICAgICAgICAgICAgIHggPSBub2RlLnBvcy5maXJzdDsKICAgICAgICAgICAgICAgIHkgPSBub2RlLnBvcy5zZWNvbmQ7CiAgICAgICAgICAgICAgICBwYXRoID0gbm9kZS5wYXRoOwogICAgICAgICAgICAgICAgcXVlLnBvcCgpOwogICAgICAgICAgICAgICAgaWYoIXBhdGguZW1wdHkoKSkgewogICAgICAgICAgICAgICAgICAgayA9IGRpcnMuZmluZChwYXRoLmJhY2soKSk7CiAgICAgICAgICAgICAgICAgICBmbGFnW3hdW3ldIHw9ICgxPDxrKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgaWYoeCA9PSBob2xlWzBdICYmIHkgPT0gaG9sZVsxXSkgewogICAgICAgICAgICAgICAgICAgIHJlcy5wdXNoX2JhY2socGF0aCk7IAogICAgICAgICAgICAgICAgICAgIGZvdW5kID0gdHJ1ZTsKICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgbnggPSB4OyBueSA9IHk7CiAgICAgICAgICAgICAgICAgICAgY291dDw8IigiPDxueDw8IiwiPDxueTw8IikiPDwidG8gIjw8cGF0aC5iYWNrKCk8PGVuZGw7CiAgICAgICAgICAgICAgICAgICAgZ2V0TmV4dChueCwgbnksIHBhdGgpOwogICAgICAgICAgICAgICAgICAgIC8vIEhpdCB0aGUgd2FsbCBDaGFuZ2UgZGlyZWN0aW9uCiAgICAgICAgICAgICAgICAgICAgaWYocGF0aC5lbXB0eSgpIHx8ICFpc1ZhbGlkKG54LCBueSwgbiwgbSkgfHwgbWF6ZVtueF1bbnldPT0xKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGZvcihrPTA7IGs8NDsgaysrKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBueCA9IHggKyBkeFtrXTsgbnkgPSB5ICsgZHlba107CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZihpc1ZhbGlkKG54LCBueSwgbiwgbSkgJiYgbWF6ZVtueF1bbnldPT0wICYmICEoZmxhZ1tueF1bbnldJigxPDxrKSkpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBxdWUucHVzaChNb3Rpb24oe254LCBueX0sIHBhdGgrZGlyc1trXSkpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvdXQ8PCJUcmFuc2ZlciB0byAiPDxwYXRoK2RpcnNba108PGVuZGw7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIAlrID0gZGlycy5maW5kKHBhdGguYmFjaygpKTsKICAgICAgICAgICAgICAgICAgICAgICAgaWYobWF6ZVtueF1bbnldPT0wICYmICEoZmxhZ1tueF1bbnldJigxPDxrKSkpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHF1ZS5wdXNoKE1vdGlvbih7bngsIG55fSwgcGF0aCkpOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGxldmVsKys7CiAgICAgICAgICAgIGlmKGZvdW5kKSB7CiAgICAgICAgICAgICAgIGNvdXQ8PCJUaGUgbWluaW11bSBzdGVwOiAiPDxsZXZlbDw8ZW5kbDsKICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0gCiAgICAgICAgfQogICAgICAgIAogICAgICAgIGlmKCFmb3VuZCkgcmV0dXJuICJpbXBvc3NpYmxlIjsKICAgICAgICBjb3V0PDwiQWxsIHNvbHV0aW9uOiAiPDxlbmRsOwogICAgICAgIGZvcihhdXRvJiBzdHIgOiByZXMpIHsKICAgICAgICAJY291dDw8c3RyPDwiLCAiOwogICAgICAgIH0KICAgICAgICBjb3V0PDxlbmRsOwogICAgICAgIHBhdGggPSByZXNbMF07CiAgICAgICAgZm9yKGkgPSAxOyBpIDwgcmVzLnNpemUoKTsgaSsrKSB7CiAgICAgICAgICAgIGlmKHBhdGguY29tcGFyZShyZXNbaV0pID4gMCkgewogICAgICAgICAgICAgICAgcGF0aCA9IHJlc1tpXTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAKICAgICAgICByZXR1cm4gcGF0aDsKICAgIH0KICAgIAogICAgYm9vbCBpc1ZhbGlkKGludCB4LCBpbnQgeSwgaW50IG4sIGludCBtKSB7CiAgICAgICAgcmV0dXJuIHg+PTAgJiYgeDxuICYmIHkgPj0wICYmIHk8bTsKICAgIH0KICAgIAogICAgdm9pZCBnZXROZXh0KGludCYgeCwgaW50JiB5LCBzdHJpbmcmIHBhdGgpIHsKICAgICAgICBpZihwYXRoLmVtcHR5KCkpIHJldHVybjsKICAgICAgICBjaGFyJiBkaXIgPSBwYXRoLmJhY2soKTsKICAgICAgICBpZihkaXI9PSd1JykgLS14OyAKICAgICAgICBlbHNlIGlmKGRpcj09J2QnKSArK3g7CiAgICAgICAgZWxzZSBpZihkaXI9PSdsJykgLS15OwogICAgICAgIGVsc2UgKyt5OwogICAgfQp9OwoKaW50IG1haW4oKSB7CiAgIAogICBTb2x1dGlvbiBzb2x2ZTsKICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBpbnB1dCA9IHt7MCwwLDAsMCwwfSx7MSwxLDAsMCwxfSx7MCwwLDAsMCwwfSx7MCwxLDAsMCwxfSx7MCwxLDAsMCwwfX07CiAgIHZlY3RvcjxpbnQ+IGJhbGwgPSB7NCwzfSwgaG9sZSA9IHswLDF9OwogICBzdHJpbmcgcmV0ID0gc29sdmUuZmluZFNob3J0ZXN0V2F5KGlucHV0LCBiYWxsLCBob2xlKTsKICAKICAgY291dDw8IlJlc3VsdDogIjw8cmV0PDxlbmRsOwogICByZXR1cm4gMDsKfQ==