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
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
#include <bitset>
#include <numeric>
#include <cmath>
#include <string>

bool checkTime(
    const std::vector<std::vector<int>> &places,
    std::pair<int,int> p,
    int time)
{
        return p.first>=0 and p.first<places.size() and p.second>=0 and p.second<places[0].size()
        and (places[p.first][p.second] > time); 
}

bool shouldContinue(
    const std::vector<std::vector<int>> &places,
    std::pair<int,int> start,
    int time)
{
    return checkTime(places, {start.first,start.second+1}, time)
        or checkTime(places, {start.first,start.second-1}, time)
        or checkTime(places, {start.first+1,start.second}, time)
        or checkTime(places, {start.first-1,start.second}, time);
  
}
void findMin(
    std::vector<std::vector<int>> &places,
    const std::vector<std::vector<std::string>>& trafficLights,
    int time,
    std::pair<int, int> start,
    std::pair<int,int> end,
    bool xxx = false)
{
    places[start.first][start.second] = std::min(places[start.first][start.second] , time);
    if(not shouldContinue(places, start, time) or (xxx and time > places[start.first][start.second] )) return;
    //
    //go right if possible
    if( checkTime(places, {start.first,start.second+1}, time)
      and ((start.first< trafficLights.size() and ('1'==(trafficLights[start.first][start.second][(time%(trafficLights[start.first][start.second].size()))])))
      or (start.first>0 and ('1'==trafficLights[start.first-1][start.second][time%(trafficLights[start.first-1][start.second].size())]))))
    {
        findMin(places, trafficLights, time, {start.first, start.second+1}, end, true);
    }

    //go left if possible
    if( checkTime(places, {start.first,start.second-1}, time)){
      if(((start.first< trafficLights.size() and ('1'==trafficLights[start.first][start.second-1][(time%(trafficLights[start.first][start.second-1].size()))]))
      or (start.first>0 and ('1'==trafficLights[start.first-1][start.second-1][time%(trafficLights[start.first-1][start.second-1].size())]))))
    {
        findMin(places, trafficLights, time, {start.first, start.second-1}, end, true);
    }}
    //go up if possible
    if( checkTime(places, {start.first-1,start.second}, time))
    { 
      if (( start.second< trafficLights[0].size() and '0'==(trafficLights[start.first-1][start.second][(time%(trafficLights[start.first-1][start.second].size()))]))
      or (start.second>0 and ('0'==trafficLights[start.first-1][start.second-1][time%(trafficLights[start.first-1][start.second-1].size())])))
    {
        findMin(places, trafficLights, time, {start.first-1, start.second}, end, true);
    }}
    //go down if possible
    if( checkTime(places, {start.first+1,start.second}, time))
    { 
      if (( start.second< trafficLights[0].size() and '0'==(trafficLights[start.first][start.second][(time%(trafficLights[start.first][start.second].size()))]))
      or (start.second>0 and ('0'==trafficLights[start.first][start.second-1][time%(trafficLights[start.first][start.second-1].size())])))
    {
        findMin(places, trafficLights, time, {start.first+1, start.second}, end, true);
    }}

    ++time;
    findMin(places, trafficLights, time, start, end);
    return;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    int m,n,q;
    std::cin>>n>>m>>q;
    std::vector<std::string> line(m, "");
    std::vector<std::vector<std::string>> trafficLights(n, line);
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j) std::cin>>trafficLights[i][j];
    }
    
    for(int i = 0;i<q;++i)
    {
        std::vector<int> x(m+1, 1000000000);
        std::vector<std::vector<int>> places(n+1, x);
        int time;
        std::pair<int,int> start, end;
        std::cin>>time
            >>start.first >>start.second
            >>end.first >>end.second;
        findMin(places, trafficLights, time, start, end);
        std::cout<<places[end.first][end.second]<<std::endl;
    }
    return 0;
}