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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAX = 100;
const int P = 840;
char s[MAX][MAX][8];
char l[MAX][MAX];

struct F {
    F* parent;
    int x, y;
    int size;
    int vid;
};

F f[P][MAX][MAX];
vector<vector<int>> g;
F* idtof[MAX*MAX*P];

F* find(F* x) {
    if(x->parent != x) {
        x->parent = find(x->parent);
        return x->parent;
    }
    return x;
}

F* unio(F* x, F* y) {
    x = find(x);
    y = find(y);
    if(x == y) return x;
    if(x->size < y->size) {
        F* tmp = x;
        x = y;
        y = tmp;
    }
    y->parent = x;
    x->size += y->size;
    return x;
}

int main() {
    ios_base::sync_with_stdio(false);
    int n , m, q;
    cin >> n >> m >> q;

    string str;
    for(int i = 1; i <= n; ++i) 
    for(int j = 1; j <= m; ++j) {
        cin >> str;
        for(int k = 0; k < str.size(); ++k) {
            s[i][j][k] = str[k];
            l[i][j] = str.size();
        }
    }

    for(int t = 0; t < P; ++t){
        for(int i = 0; i <= n; ++i) 
        for(int j = 0; j <= m; ++j) {
            f[t][i][j].parent = &f[t][i][j];
            f[t][i][j].x = i;
            f[t][i][j].y = j;
            f[t][i][j].size = 1;
            f[t][i][j].vid = -1;
        }
        for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) {
            if(s[i][j][t%l[i][j]] == '0') {
                unio(&f[t][i-1][j-1], &f[t][i][j-1]);
                unio(&f[t][i-1][j], &f[t][i][j]);
            } else {
                unio(&f[t][i-1][j-1], &f[t][i-1][j]);
                unio(&f[t][i][j-1], &f[t][i][j]);
            }
        }
        for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= m; ++j) {
            if(f[t][i][j].parent == &f[t][i][j] && f[t][i][j].vid == -1) {
                int id = g.size();
                g.push_back(vector<int>());
                idtof[id] = &f[t][i][j];
                f[t][i][j].vid = id;
            }
        }
    }

    for(int t = 0; t < P; ++t){
        for(int i = 0; i <= n; ++i) 
        for(int j = 0; j <= m; ++j) {
            int r1 = find(&f[t][i][j])->vid;
            int r2 = find(&f[(t+1)%P][i][j])->vid;
            g[r1].push_back(r2);
        }
    }

    for(int i = 0; i < g.size(); ++i) {
        sort(g[i].begin(), g[i].end());
        g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
    }
    
   
   while(q--) {
       int t, a, b, c, d;
       cin >> t >> a >> b >> c >> d;
       
        deque<pair<int, F*>> que;
        F* fab = find(&f[t%P][a][b]);
        que.push_back(make_pair(0, fab));
        if(fab == find(&f[t%P][c][d])) {
            cout << t << '\n';
            continue;
        }
        bool ok = false;
        while(!ok) {
            pair<int, F*> front = que.front();
            que.pop_front();
            int v = front.second->vid;
            int t2 = front.first;
            for(int i = 0; i < g[v].size(); ++i) {
                F* ff =  idtof[g[v][i]];
                if(find(&f[(t+t2+1)%P][c][d]) == ff) {
                    cout << t+t2+1 << '\n';
                    ok = true;
                    break;
                }
                que.push_back(make_pair(t2+1, ff));
            }
        }   
   }
}