//#include #include #include #include #include #include #include #include #include #include #include using namespace std; bool DBG = false; /* * generics for HackerRank problems. */ vector V; uint32_t N, R, C; // generics N = sizeof(V), R,C = sizeof M... UINT32_MAX string S; #define SORT(x) sort(x.begin(), x.end()); #define RSORT(x) sort(x.begin(), x.end(), mygreater()); struct mygreater { template bool operator()(T const &a, T const &b) const { return a > b; } }; #define MAXN 200 #define MAXDIST (MAXN * MAXN) class Point2d { public: int x, y; string S; }; class SearchNode // generic hackerrank class { public: SearchNode() {val = MAXDIST;}; int32_t val; // minimum distance Point2d parent; //who's my daddy? string S; friend std::ostream& operator<<(std::ostream &os, const SearchNode &HR); }; // for displaying HRGeneric class std::ostream& operator<<(std::ostream& out, const SearchNode& C) { out << "(" << C.val <<":"<< C.S << ")"; return out; } vector > MH; // matrix of the generic class; //display a vector. template ostream& operator<< (ostream &out, const vector &a) { if (!a.empty()) { out << '['; copy(a.begin(), a.end(), ostream_iterator(out, " ")); out << "\b]"; } return out; } //display a matrix. template ostream& operator<< (ostream &out, const vector> &a) { int sz = a.size(); for(int i = 0; i < sz; i++) { int sz2 = a[i].size(); for(int j = 0; j < sz2; j++) { out << a[i][j] << ' '; } out << endl; } return out; } // initialize the matrix - r rows, c columns template void initM(vector> & myM, int r, int c) { myM.resize(r); for (int i = 0; i < r; i ++){ myM[i].resize(c); } } Point2d goNext(int &i, Point2d pt) { Point2d ans; switch (i) { case 0: ans.x = pt.x - 2; ans.y = pt.y - 1; ans.S = "UL"; if (ans.x >= 0 && ans.y >= 0) break; i++; case 1: ans.x = pt.x - 2; ans.y = pt.y + 1; ans.S = "UR"; if (ans.x >=0 && ans.y < N) break; i++; case 2: ans.x = pt.x; ans.y = pt.y + 2; ans.S = "R"; if (ans.y < N) break; i++; case 3: ans.x = pt.x + 2; ans.y = pt.y + 1; ans.S = "LR"; if (ans.x < N && ans.y < N) break; i++; case 4: ans.x = pt.x + 2; ans.y = pt.y - 1; ans.S = "LL"; if (ans.x < N && ans.y >=0 ) break; i++; case 5: ans.x = pt.x; ans.y = pt.y - 2; ans.S = "L"; if (ans.y >= 0) break; i++; default: ans.x = 0; ans.y = 0; S = ""; } return ans; } void getShortestPath(Point2d pt, Point2d pend) { std::queue bfs; bfs.push(pt); while (!bfs.empty()) { Point2d tmpPt = bfs.front(); Point2d pt2; bfs.pop(); DBG && cout << MH < MH[tmpPt.x][tmpPt.y].val + 1) { bfs.push(pt2); // set the matrix accordingly MH[pt2.x][pt2.y].parent = tmpPt; MH[pt2.x][pt2.y].val = MH[tmpPt.x][tmpPt.y].val+1; MH[pt2.x][pt2.y].S = pt2.S; } } } } } void solve() { cin >> N; int istart, jstart, iend, jend; cin >> istart >> jstart >> iend >> jend; initM(MH, N, N); Point2d pt; pt.x = istart; pt.y = jstart; Point2d pend; pend.x = iend; pend.y = jend; MH[istart][jstart].parent = pt; MH[istart][jstart].val = 0; getShortestPath(pt, pend); DBG && cout << MH; if (MH[iend][jend].val == MAXDIST) { cout << "Impossible" << endl; return; } vector mylist; cout << MH[iend][jend].val << endl; while (!(pend.x == pt.x && pend.y == pt.y)) { mylist.push_back(MH[pend.x][pend.y].S); pend = MH[pend.x][pend.y].parent; } for (int i = mylist.size()-1; i >= 0 ; i --) { cout << mylist[i] << " "; } cout << endl; } int main(int argc, char * argv[]) { if ( argc > 1 && !strcmp(argv[1], "-d")) DBG = true; solve(); return 0; }