Miscellany

#include<iostream>
using namespace std;
#define MAX 1002
struct ADD_LIST
{
    int f_row,f_col,t_row,t_col;
};
struct BFS_LIST
{
    int row,col,index;    
};
BFS_LIST bfs_start,bfs_temp,bfs_next,bfs_end,bfs[100000];
ADD_LIST add_start,add_temp,add_next,add[100000];        
int n,m,start_row,start_col,wall,add_count,answer_count=0,target_row,target_col,bfs_cnt=0;
int from_row,from_col,to_row,to_col,array[MAX][MAX],answer[100000],target_count,add_cnt=0,in=0;
void add_path(void)
{
    scanf("%d",&add_count);
    for(int i=0;i<add_count;i++)
    {
        scanf("%d %d %d %d",&from_row,&from_col,&to_row,&to_col);
        
        
        add_start=add[0];
        add[add_cnt].f_row=from_row;
        add[add_cnt].f_col=from_col;
        
        add[add_cnt].t_row=to_row;
        add[add_cnt++].t_col=to_col;        
        
        array[from_row][from_col]=2;
    }   
}
int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    scanf("%d",&start_row);
    scanf("%d",&start_col);
    
    bfs[bfs_cnt].index=-1;
    bfs[bfs_cnt].row=start_row;
    bfs[bfs_cnt++].col=start_col;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           scanf("%d",&array[i][j]);
    
    add_path();
    
    scanf("%d",&target_count);
    for(int i=0;i<target_count;i++)
    {
        scanf("%d",&target_row);
        scanf("%d",&target_col);
        array[target_row][target_col]=3;
    }    
    
    int flag=0;
    bfs_next=bfs_end=bfs[0];
 
    int end_cnt=0,end_cnt1;
    while(end_cnt!=bfs_cnt)
    {
        bfs_next=bfs[end_cnt];
        if(array[bfs_next.row][bfs_next.col]==3)
        {
            end_cnt1=bfs_next.index;
            answer[answer_count++]=bfs_next.col;
            answer[answer_count++]=bfs_next.row;
            while(end_cnt1!=-1)
            {
                answer[answer_count++]=bfs[end_cnt1].col;
                answer[answer_count++]=bfs[end_cnt1].row;
                end_cnt1=bfs[end_cnt1].index;
            }   
            flag=1;
            break;
        }
        int ff=0;
        if(array[bfs_next.row][bfs_next.col]==2)
        {
            ff=1;
            array[bfs_next.row][bfs_next.col]=1;
            end_cnt1=0;
            while(end_cnt1!=add_cnt)
            {
                if((add[end_cnt1].f_row==bfs_next.row)&&(add[end_cnt1].f_col==bfs_next.col))
                {
                    bfs[bfs_cnt].row=add[end_cnt1].t_row;
                    bfs[bfs_cnt].col=add[end_cnt1].t_col;
                    bfs[bfs_cnt++].index=in;
                }
                end_cnt1++;
            }
        }
        if((array[bfs_next.row][bfs_next.col]==0)||(ff==1))
        {
            array[bfs_next.row][bfs_next.col]=1;
            if(bfs_next.row-1>0)
            {
                if(array[bfs_next.row-1][bfs_next.col]!=1)
                {
                    bfs[bfs_cnt].row=bfs_next.row-1;
                    bfs[bfs_cnt].col=bfs_next.col;
                    bfs[bfs_cnt++].index=in;
                }
            } 
            if(bfs_next.row+1<=n)
            {
                if(array[bfs_next.row+1][bfs_next.col]!=1)
                {
                    bfs[bfs_cnt].row=bfs_next.row+1;
                    bfs[bfs_cnt].col=bfs_next.col;
                    bfs[bfs_cnt++].index=in;
                }
            }
            if(bfs_next.col+1<=m)
            {
                if(array[bfs_next.row][bfs_next.col+1]!=1)
                {
                    bfs[bfs_cnt].row=bfs_next.row;
                    bfs[bfs_cnt].col=bfs_next.col+1;
                    bfs[bfs_cnt++].index=in;
                }
            }
            if(bfs_next.col-1>0)
            {
                if(array[bfs_next.row][bfs_next.col-1]!=1)
                {
                    bfs[bfs_cnt].row=bfs_next.row;
                    bfs[bfs_cnt].col=bfs_next.col-1;
                    bfs[bfs_cnt++].index=in;
                }
            }
        }
        end_cnt++;
        in++;
     }    
     if(flag==1)
     {
         bool val=true;
         cout<<endl<<(answer_count>>1)<<endl;
         for(int i=answer_count-1;i>=0;i--)
         {
              if(val==true)
                   cout<<answer[i]<<" ";
              else
                   cout<<answer[i]<<endl;
              val=!val;
         }    
     }
     else
          cout<<"Impossible"; 
}