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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
#define debug(...) __VA_ARGS__
#else
#define debug(...) {}
#endif
int n,m,q;
bool vis[1000001];
int konw(int a, int b){
    return a*(m+2)+b;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i;
    cin>>n>>m>>q;
    string tab[n+1][m+1];
    for (i = 1; i < n+1 ; i++) for (int j = 1; j < m+1; j++) cin>>tab[i][j];
    while (q--){
        int t,a,b,c,d;
        cin>>t>>a>>b>>c>>d;
        if (a == c && b == d){
            cout<<t<<"\n";
            continue;
        }
        for (i = 0; i < n+2; i++) for (int j = 0; j < m+2; j++) vis[konw(i,j)] = 0;
        vis[konw(a,b)] = 1;       
        while (!vis[konw(c,d)]){
            vector<int> sas[(n+4)*(m+4)];
            for (i = 1; i < n+1; i++){
                for (int j = 1; j < m+1; j++){
                    if (tab[i][j][t%int(tab[i][j].size())] == '1'){
                        sas[konw(i-1,j-1)].push_back(konw(i-1,j));
                        sas[konw(i-1,j)].push_back(konw(i-1,j-1));
                        sas[konw(i,j-1)].push_back(konw(i,j));
                        sas[konw(i,j)].push_back(konw(i,j-1));
                    }else{
                        sas[konw(i-1,j-1)].push_back(konw(i,j-1));
                        sas[konw(i,j-1)].push_back(konw(i-1,j-1));
                        sas[konw(i-1,j)].push_back(konw(i,j));
                        sas[konw(i,j)].push_back(konw(i-1,j));
                    }
                }   
            }
            queue<int> Q;
            for (i = 0; i < n+2; i++) for (int j = 0; j < m+2; j++) if (vis[konw(i,j)]) Q.push(konw(i,j));
            while (Q.size()){
                int v = Q.front();
                vis[v] = 1;
                Q.pop();
                for (int u : sas[v]){
                    if (!vis[u]){
                        vis[u] = 1;
                        Q.push(u);
                    }
                }
            }
            t++;
            /*/for (i = 0; i < n+1; i++){
                for (int j = 0; j < m+1; j++) cout<<vis[konw(i,j)]<<" ";
                cout<<"\n";
            }
            cout<<t<<"\n";/*/
        }
        cout<<t-1<<"\n";
    }
    return 0;
}