Optimized_Endoscope_Samsung

#include <iostream>
using namespace std;

class que{
    int *row;
    int *col;
    int *len;
    int front,rear;
    public:
        que();
        que(int r,int c){
            row= new int[r*c];
            col= new int[r*c];
            len= new int[r*c];
            front=rear=0;
        }

        void push(int x,int y, int z){
            row[rear]=x;
            col[rear]=y;
            len[rear]=z;
            rear++;
        }

        void pop(){
            front++;
        }

        void top(int &x, int &y, int &z){
            x=row[front];
            y=col[front];
            z=len[front];
        }

        bool empty(){
            return front==rear;
        }
};

int r,c,x,y,len;
int a[1000][1000];
bool visited[1000][1000];
int ans;

bool valid(int x, int y){
    if(x>=0 && x<r && y>=0 && y<c && visited[x][y]==false)
        return true;
    return false;
}

void init(){
    for(int i=0; i<1000; i++)
        for(int j=0; j<c; j++)
            visited[i][j]=false;
}

void bfs(){
    if(a[x][y]==0) return;
    ans=1;

    que q(r,c);
    q.push(x,y,1);
    visited[x][y]=true;

    while(!q.empty()){
        int x,y,l;
        q.top(x,y,l);
        q.pop();

        // up 1 2 4 7 down 1 2 5 6  left 1 3 6 7 right 1 3 4 5

        //for going up
        if(valid(x-1,y) && l+1<=len){
            if(a[x-1][y]==1 || a[x-1][y]==2 || a[x-1][y]==5 || a[x-1][y]==6){
                if(a[x][y]==1 || a[x][y]==2 || a[x][y]==4 || a[x][y]==7){
                    visited[x-1][y]=true;
                    q.push(x-1,y,l+1);
                    ans++;
                }
            }
        }

        //for down
        if(valid(x+1,y) && l+1<=len){
            if(a[x+1][y]==1 || a[x+1][y]==2 || a[x+1][y]==4 || a[x+1][y]==7){
                if(a[x][y]==1 || a[x][y]==2 || a[x][y]==5 || a[x][y]==6){
                    visited[x+1][y]=true;
                    q.push(x+1,y,l+1);
                    ans++;
                }
            }
        }

        //for left
        if(valid(x,y-1) && l+1<=len){
            if(a[x][y-1]==1 || a[x][y-1]==3 || a[x][y-1]==4 || a[x][y-1]==5){
                if(a[x][y]==1 || a[x][y]==3 || a[x][y]==6 || a[x][y]==7){
                    visited[x][y-1]=true;
                    q.push(x,y-1,l+1);
                    ans++;
                }
            }
        }

        //for right
        if(valid(x,y+1) && l+1<=len){
            if(a[x][y+1]==1 || a[x][y+1]==3 || a[x][y+1]==6 || a[x][y+1]==7){
                if(a[x][y]==1 || a[x][y]==3 || a[x][y]==4 || a[x][y]==5){
                    visited[x][y+1]=true;
                    q.push(x,y+1,l+1);
                    ans++;
                }
            }
        }

    }

}

int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>r>>c>>x>>y>>len;

        for(int i=0; i<r; i++)
            for(int j=0; j<c; j++)
                cin>>a[i][j];

        init();

        ans=-1;
        bfs();
        cout<<ans<<endl;
    }
    return 0;
}