#include #include using namespace std; enum{UL=0,UR,R,LR,LL,L}; const char *DIRNAME[] = {"UL","UR","R","LR","LL","L"}; int gridN,targetX,targetY; bool *dup; class res{ public: res(int initX,int initY){ x = initX; y = initY; nMove = 0; } res(res *init,int dir){ x = init->x; y = init->y; nMove = init->nMove+1; history = init->history; history.push_back(dir); switch(dir){ case UL: x-=1;y-=2; break; case UR: x+=1;y-=2; break; case R : x+=2; break; case LR: x+=1;y+=2; break; case LL: x-=1;y+=2; break; case L : x-=2; break; } discard = ( (x<0) || (y<0) || (x>=gridN) || (y>=gridN) || dup[(y*gridN)+x]); done = ( (x==targetX) && (y==targetY) ); } int x; int y; int nMove; bool done,discard; vector history; }; int main(){ int startX,startY; cin>>gridN>>startY>>startX>>targetY>>targetX; if( (startX==targetX) && (startY==targetY) ){ cout << 0 << endl << endl; return 0; } dup = new bool[gridN*gridN]; for(int i=0,iS=gridN*gridN;i complete; vector resList,resNewList; resList.push_back(new res(startX,startY)); for(int i=0;(!done)&&(resList.size()<1000000)&&(i<1000000);i++){ for(int iR=0,iRS=resList.size();(!done)&&(resNewList.size()<1000000)&&(iRdone){ done = 1; complete.push_back(r); } if(r->discard){delete r;} else{resNewList.push_back(r);} } delete resList.at(iR); } if(resNewList.size()>=1000000)break; resList.clear(); resList = resNewList; resNewList.clear(); for(int i2=0,i2S=resList.size();i2y)+nd->x] = 1; } } if(complete.size()>1){ int lowestMove; for(int i=0,iS=complete.at(0)->nMove;idiscard)continue; lowestMove = min(lowestMove,nd->history.at(i)); } for(int i2=0,i2S=complete.size();i2discard)continue; if(nd->history.at(i)>lowestMove)nd->discard = 1; } } for(int i=complete.size()-1;i>-1;i--){ if(complete.at(i)->discard)complete.erase(complete.begin()+i); } } if(!complete.size())cout << "Impossible"; else{ res *nd = complete.at(0); cout << nd->nMove << endl; for(int i2=0,i2S=nd->history.size();i2history.at(i2)] << " "; } } return 0; }