#include #include #include using namespace std; #define GETX(_x, _n) (_x/n) #define GETY(_y, _n) (_y%n) #define SERIALIZE(_x, _y, _n) ((_x)*(_n) + (_y)) #define CHECK(p) (p>=0&&p q; vector visited(n*n); vector< pair > parent(n*n); int lmost, mincount=0, done=0; int start = SERIALIZE(i_start, j_start, n); int end = SERIALIZE(i_end, j_end, n); q.push(start); visited[start]=1; parent[start].first=-1; parent[start].second=-1; lmost=start; #ifdef DEBUG cout << "Finding shortest path from " << start << " to " << end << endl; #endif /*DEBUG*/ while(q.size() and !done) { int front=q.front(), child=0; q.pop(); if (lmost==front) { lmost=-1; mincount++; } PATH path = PATH_START; int i=GETX(front,n),j=GETY(front,n); while (PMAX != path) { child=getNext(path, n, i, j); if (-1 == child) continue; if (child==end) { visited[end]=1; parent[child].first=front; parent[child].second=path; done=1; break; } if (!visited[child]) { parent[child].first=front; parent[child].second=path; #ifdef DEBUG cout << "Visiting node " << child << " from " << front << " (" < path=parent[end]; vector path_str; while (path.first!=-1) { path_str.push_back(getPathStr((PATH)path.second)); path=parent[path.first]; } for(int i=path_str.size()-1; i>=0; --i) { cout << path_str[i] << " "; } cout << endl; } else { cout << "Impossible" << endl; } } int main() { int n; cin >> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }