#include #include #include #include #include #include #include #include #include #define LL long long int #define P(N) printf("%d\n",N); #define S(N) scanf("%d",&N); #define SL(N) scanf("%lld",&N); #define pb push_back #define mp make_pair #define pnl printf("\n"); #define FOR(i,a,b) for (i=a;i<=b;i++) #define mem(a,val) memset(a,val,sizeof(a)) using namespace std; int gcd(int a, int b){ int temp; while(b>0) { temp= b; b=a%b; a=temp;} return a;} int N; vectorfinal_path; vector< pair >adj[40010]; bool vis[40010]; pairparent[40010]; struct move { int dx; int dy; string dir; }; struct move moves[6]; bool is_valid(int x, int y) { if(x >= 0 && x < N && y >= 0 && y < N) { return true; } else { return false; } } void addMoves() { // UL, UR, R, LR, LL, L moves[0].dx = -2, moves[0].dy = -1, moves[0].dir = "UL"; moves[1].dx = -2, moves[1].dy = 1, moves[1].dir = "UR"; moves[2].dx = 0, moves[2].dy = 2, moves[2].dir = "R"; moves[3].dx = 2, moves[3].dy = 1, moves[3].dir = "LR"; moves[4].dx = 2, moves[4].dy = -1, moves[4].dir = "LL"; moves[5].dx = 0, moves[5].dy = -2, moves[5].dir = "L"; } void print_path(int src, int node) { if(node <= 0 || node == src) { return; } print_path(src, parent[node].first); cout< >que; que.push(mp(src,0)); vis[src] = true; while(!que.empty()) { pair pa = que.front(); que.pop(); int node = pa.first; int level = pa.second; if(node == dest) { return level; } int len = adj[node].size(); for(int i = 0 ;i< len;i++) { int u = adj[node][i].first; if(!vis[u]) { vis[u] = true; que.push(mp(u, level + 1)); parent[u] = mp(node, adj[node][i].second); } } } return -1; } int getNode(int x, int y) { return x*N+y; } void buildGraph() { for(int x = 0;x< N;x++) { for(int y = 0;y>N; addMoves(); buildGraph(); cin>>start_x>>start_y>>end_x>>end_y; int src = getNode(start_x, start_y); int dest = getNode(end_x, end_y); parent[src] = mp(src, ""); int ret = bfs(src, dest); if(ret == -1) { printf("Impossible"); } else { printf("%d\n", ret); print_path(src, dest); } pnl return 0; }