Anonymous

#include<iostream>#include<string>#include<cstdio>#include<algorithm>#include<vector>#include<map>#include<list>#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]; bool paths[1001];//map<int,map<int,vector<int> > > mp;int x,y,stx,sty;int exits;int main(){    cin>>x>>y;    cin>>stx>>sty;    stx--;    sty--;    REP(i,0,x) REP(j,0,y) {        scanf("%d",&cells[i][j].trav);        cells[i][j].exit=false;        cells[i][j].prevx=cells[i][j].prevy=-1;        cells[i][j].trav=0;    }    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;    point res;    while(!q.empty()){        point a=q.front();        q.pop();        x1=a.x;        y1=a.y;        if(cells[x1][y1].exit==true) {            res.x=x1;            res.y=y1;            //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;        }        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;        }        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;        }        int sz=SZ(cells[x1][y1].lt);        REP(i,0,sz){            q.push(cells[x1][y1].lt[i]);            cells[cells[x1][y1].lt[i].x][cells[x1][y1].lt[i].y].prevx=x;            cells[cells[x1][y1].lt[i].x][cells[x1][y1].lt[i].y].prevy=y;            cells[cells[x1][y1].lt[i].x][cells[x1][y1].lt[i].y].trav=1;        }    }        if(flag){        stack<point> stk;        stk.push(res);        while(res.x!=-1){            cout<<res.x+1<<"  "<<res.y+1<<endl;            res.x=cells[res.x][res.y].prevx;            res.y=cells[res.x][res.y].prevy;            getchar();            stk.push(res);        }        cout<<stk.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;}