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
#include <cstdio>
#include <cstring>
#include <vector>
#define MAKS 1100000
#define INF 2000000000
using namespace std;
int nast[MAKS][2][8];
char slen[MAKS];
int wyn[MAKS];
vector<int> kol[8];
int dd[4][7]={
    {0,-1,  0,0, 1,0,  1},
    {0,1,   0,1, 1,1,  1},
    {-1,0,  0,0, 0,1,  0},
    {1,0,   1,0, 1,1,  0},
};

int main()
{
    int n,m,q;
    scanf("%d %d %d",&n,&m,&q);
    int N=n+1; int M=m+1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            char s[9];
            scanf("%s",s);
            int v=i*m+j;
            slen[v]=strlen(s);
            for(int z=0;z<2;z++)
            {
                int p=0; while(s[p]!=('0'+z))p++;
                //printf("p: %d\n",p);
                nast[v][z][p]=0;
                int akt=0;
                int cnt=slen[v]-1;
                while(cnt--)
                {
                    if(p==0)p=slen[v]-1;
                    else p--;
                    if(s[p]==('0'+z))akt=0;
                    else akt++;
                    nast[v][z][p]=akt;
                    //printf("dla p: %d -> %d\n",p,akt);
                }
                //printf("z=%d ",z);
                //for(int pp=0;pp<slen[v];pp++)printf("%d ",nast[v][z][pp]);
                //puts("");
            }
        }
    }
    for(int zap=1;zap<=q;zap++)
    {
        for(int i=0;i<=N*M;i++)wyn[i]=INF;

        int tq,a,b,c,d;
        scanf("%d %d %d %d %d",&tq,&a,&b,&c,&d);

        for(int z=0;z<8;z++)kol[z].clear();
        int cel=c*M+d;
        int t=tq; int tmod=tq%8;

        kol[tmod].push_back(a*M+b);
        wyn[a*M+b]=t;
        while(true)
        {
            while(kol[tmod].empty())
            {
                t++; tmod++;
                if(tmod==8)tmod=0;
            }
            int v=kol[tmod].back(); kol[tmod].pop_back();
            if(wyn[v]!=t)continue;
            if(v==cel)
            {
                printf("%d\n", t);
                break;
            }
            int vi=v/M; int vj=v%M;
            //printf("vi: %d, vj:%d\n",vi,vj);
            for(int z=0;z<4;z++)
            {
                int ui=vi+dd[z][0]; int uj=vj+dd[z][1];
                if(ui<0 || ui>n || uj<0 || uj>m)continue;
                //printf("ui: %d, uj: %d\n",ui,uj);
                int u=ui*M+uj;

                int dt=8; int si,sj;
                si=vi+dd[z][2]-1; sj=vj+dd[z][3]-1;
                if(si>=0 && si<n && sj>=0 && sj<m)dt=min(dt,nast[si*m+sj][dd[z][6]][t%slen[si*m+sj]]);
                si=vi+dd[z][4]-1; sj=vj+dd[z][5]-1;
                if(si>=0 && si<n && sj>=0 && sj<m)dt=min(dt,nast[si*m+sj][dd[z][6]][t%slen[si*m+sj]]);


                if(t+dt<wyn[u])
                {
                    wyn[u]=t+dt;
                    kol[(t+dt)%8].push_back(u);
                }
            }
        }

    }
}