rendered paste body#include<iostream>#include<string>#include<cstdio>#include<algorithm>#include<vector>#include<map>#include<queue>#include<stack>using namespace std;#define REP(i,j,n) for(int i=j;i<n;i++)#define SZ(x) (x).size()#define PB push_backclass point{ public: int x,y; point(int a=0,int b=0) { x=a; y=b; } }; struct cell{ int prevx,prevy; int trav; bool path; bool exit; vector<point> lt;}cells[1001][1001];//map<int,map<int,vector<int> > > mp;int x,y,stx,sty;int exits;void display(){ REP(i,0,x){ REP(j,0,y) cout<<cells[i][j].trav<<" "; cout<<endl; } cout<<endl;} int main(){ cin>>x>>y; cin>>stx>>sty; stx--; sty--; REP(i,0,x) REP(j,0,y) { cells[i][j].prevy=-1; cells[i][j].prevx=-1; scanf("%d",&cells[i][j].trav); cells[i][j].exit=false; } cells[stx][sty].trav=1; cells[stx][sty].prevx=-1; cells[stx][sty].prevy=-1; int path; cin>>path; int x1,y1,x2,y2; REP(i,0,path) { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); cells[x1-1][y1-1].path=true; cells[x1-1][y1-1].lt.PB(point(x2-1,y2-1)); } cin>>exits; REP(i,0,exits){ scanf("%d %d",&x1,&y1); cells[x1-1][y1-1].exit=true; } queue<point> q; q.push(point(stx,sty)); bool flag=false; int markx,marky; while(!q.empty()){ point a=q.front(); q.pop(); x1=a.x; y1=a.y; if(cells[x1][y1].exit==true) { markx=x1; marky=y1; // cout<<cells[x1][y1].prevx<<" "<<cells[x1][y1].prevy<<endl; //cout<<res.x+1<<" "<<res.y+1<<endl; flag=true; break; } if((x1-1)>-1&&cells[x1-1][y1].trav==0){ q.push(point(x1-1,y1)); cells[x1-1][y1].trav=1; cells[x1-1][y1].prevx=x1; cells[x1-1][y1].prevy=y1; // cout<<x1-1<<" "<<y1<<endl; } if((y1-1)>-1&&cells[x1][y1-1].trav==0){ q.push(point(x1,y1-1)); cells[x1][y1-1].trav=1; cells[x1][y1-1].prevx=x1; cells[x1][y1-1].prevy=y1; } if((y1+1)<y&&cells[x1][y1+1].trav==0){ q.push(point(x1,y1+1)); cells[x1][y1+1].trav=1; cells[x1][y1+1].prevx=x1; cells[x1][y1+1].prevy=y1; // cout<<x1<<" "<<y1+1<<endl; // cout<<cells[x1][y1+1].prevx<<" "<<cells[x1][y1+1].prevy<<" "; // cout<<x1<<" "<<y1<<endl; } if((x1+1)<x&&cells[x1+1][y1].trav==0){ q.push(point(x1+1,y1)); cells[x1+1][y1].trav=1; cells[x1+1][y1].prevx=x1; cells[x1+1][y1].prevy=y1; // cout<<x1+1<<" "<<y1<<endl; } int sz=SZ(cells[x1][y1].lt); REP(i,0,sz){ int k1=cells[x1][y1].lt[i].x,k2=cells[x1][y1].lt[i].y; if(cells[k1][k2].trav==0){ q.push(cells[x1][y1].lt[i]); cells[k1][k2].prevx=x1; cells[k1][k2].prevy=y1; cells[k1][k2].trav=1; } } // display(); // cout<<endl<<endl; // getchar(); } point res(markx,marky); /* cout<<cells[0][3].prevx<<" "<<cells[0][3].prevy<<" "<<res.x<<" "<<res.y<<endl; cout<<cells[1][3].prevx<<" "<<cells[1][3].prevy<<endl; cout<<cells[2][0].prevx<<" "<<cells[2][0].prevy<<endl; cout<<cells[1][0].prevx<<" "<<cells[1][0].prevy<<endl;*/ if(flag){ stack<point> stk; stk.push(res); int size=1; while(stk.top().x!=-1&&stk.top().y!=-1){// cout<<res.x<<" "<<res.y<<endl;// cout<<res.x+1<<" "<<res.y+1<<endl; size++; res=stk.top(); stk.push(point(cells[res.x][res.y].prevx,cells[res.x][res.y].prevy)); } if(size>1) { stk.pop(); cout<<size-1<<endl; } else cout<<size<<endl; while(!stk.empty()){ cout<<stk.top().x+1<<" "<<stk.top().y+1<<endl; stk.pop(); } //cout<<"POSSIBLE"<<endl; } else cout<<"Impossible"<<endl; //cin>>x; return 0;}