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
#include <bits/stdc++.h>
using namespace std;

int n, m, q; // n rows, m columns, q querries
int t, a, b, c, d;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> Q;

int how_long(int time, string *crossroads, char direction) {
    if (crossroads->size() < 2) {
        return INT_MAX;
    }

    int r = time % (crossroads->size() / 2);
    return crossroads->find_first_of(direction, r) - r;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> q;

    string crossroads[n + 7][m + 7];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> crossroads[i][j];
            crossroads[i][j] += crossroads[i][j];
        }
    }

    for (int querry = 0; querry < q; querry++) {
        cin >> t >> a >> b >> c >> d;
        Q.push({t, {a, b}});

        int plazas[n + 7][m + 7];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                plazas[i][j] = INT_MAX;
            }
        }

        while(!Q.empty()) {
            int time = Q.top().first;
            int row = Q.top().second.first;
            int col = Q.top().second.second;
            Q.pop();

            if (time >= plazas[row][col]) {
                continue;
            }
            plazas[row][col] = time;

            // go up
            if (row > 0) {
                int waiting_time = min(how_long(time, &crossroads[row][col], '0'), how_long(time, &crossroads[row][col + 1], '0'));
                Q.push({time + waiting_time, {row - 1, col}});
            }

            // go down
            if (row < n) {
                int waiting_time = min(how_long(time, &crossroads[row + 1][col], '0'), how_long(time, &crossroads[row + 1][col + 1], '0'));
                Q.push({time + waiting_time, {row + 1, col}});
            }

            // go left
            if (col > 0) {
                int waiting_time = min(how_long(time, &crossroads[row][col], '1'), how_long(time, &crossroads[row + 1][col], '1'));
                Q.push({time + waiting_time, {row, col - 1}});
            }

            // go right
            if (col < m) {
                int waiting_time = min(how_long(time, &crossroads[row][col + 1], '1'), how_long(time, &crossroads[row + 1][col + 1], '1'));
                Q.push({time + waiting_time, {row, col + 1}});
            }
        }

        cout << plazas[c][d] << "\n";
    }

    return 0;
}