1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
short p[15000+5][15000+5];
char p2[15000+5][15000+5];
int n,m;

int tmpx[4]={0,1,0,-1};
int tmpy[4]={1,0,-1,0};

bool zwroc_ity_bit(int a, int i, int p2){
    return a & (1<<(p2-i-1));
}


int ile_czasu_do_zielonego_skrz(long long t, int x, int y, int kier){
    if (x<0 || x>=m ||y<0 || y>=n){
        return 10;
    }
    int b=p[x][y];
    int rozm = p2[x][y];
    int licznik=0;
    for (int i=0; i<rozm;i++){
        if (zwroc_ity_bit(b,((long long)i+t)%(long long)rozm,rozm)==kier%2){
            return licznik;
        }else{
            licznik++;
        }
    }
    cout << x<<" "<<y<<" "<<kier<<"PROBLEM"<<endl;
    return -1;
}

int ile_czasu_do_zielonego_pl(long long t, int x, int y,int kier){
    if (kier==0){
        return min(ile_czasu_do_zielonego_skrz(t,x,y,kier),ile_czasu_do_zielonego_skrz(t,x-1,y,kier));
    }
    if (kier==1){
        return min(ile_czasu_do_zielonego_skrz(t,x,y,kier),ile_czasu_do_zielonego_skrz(t,x,y-1,kier));
    }
    if (kier==2){
        return min(ile_czasu_do_zielonego_skrz(t,x-1,y-1,kier),ile_czasu_do_zielonego_skrz(t,x,y-1,kier));
    }
    if (kier==3){
        return min(ile_czasu_do_zielonego_skrz(t,x-1,y,kier),ile_czasu_do_zielonego_skrz(t,x-1,y-1,kier));
    }
}
//x <= m
//y<=n
int symuluj(int xa, int ya, int xb, int yb,long long t){

priority_queue<pair<long long,pair <int,int> > ,vector<pair<long long,pair <int,int> > >, greater<pair<long long,pair <int,int> >> > q;
vector <vector <long long> > e;
e.resize(m+1);
for (int i=0; i<=m;i++){
    e[i].resize(n+1,-1);
}

e[xa][ya]=t;
q.push(make_pair(t,make_pair(xa,ya)));

while(!q.empty()){
    pair<long long, pair<int,int> > tmp = q.top();
    int tmp_x=tmp.second.first;
    int tmp_y=tmp.second.second;
    //cout <<" x:"<<tmp_x<<" y:"<<tmp_y<<" t:"<<tmp.first<<endl;
    q.pop();
    for (int i=0; i<4;i++){
        int x=tmp_x + tmpx[i];
        int y=tmp_y + tmpy[i];
        if (x >= 0 && x<m+1 && y>=0 && y<n+1){
            if (e[x][y]==-1 || e[x][y]>e[tmp_x][tmp_y]+ile_czasu_do_zielonego_pl(e[tmp_x][tmp_y],tmp_x,tmp_y,i)){
                e[x][y]=e[tmp_x][tmp_y]+ile_czasu_do_zielonego_pl(e[tmp_x][tmp_y],tmp_x,tmp_y,i);
                q.push(make_pair (e[tmp_x][tmp_y]+ile_czasu_do_zielonego_pl(e[tmp_x][tmp_y],tmp_x,tmp_y,i), make_pair(x,y)));
            }
        }
    }
}
return e[xb][yb];

}


int main(){
int q;
cin >> n >> m >> q;

for (int i=0; i<n;i++){
    for (int j=0; j<m;j++){
        string tmp;
        cin >> tmp;
        int a=0;
        for (int k=tmp.size()-1;k>=0;k--){
            a+=(1<<(tmp.size()-k-1))*(tmp[k]=='1');
        }
        p[j][i]=a;
        p2[j][i]=tmp.size();
    }
}
for (int q2=0;q2<q;q2++){
    long long t;
    int a1, a2, b1, b2;
    cin >> t >> a1>>a2>>b1>>b2;
    cout << symuluj(a2,a1,b2,b1,t)<<endl;
}

}