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
133
134
135
//Mateusz Piórkowski
#include <iostream>
#include <vector>
#include <string>
#include <queue>

//struct plac{};
struct road;
struct plac;

struct plac{
	std::vector<road> roads;
	int i,j;
	bool explored;
};
struct road{
	bool cycles[8];
	unsigned char cycles_n;
	plac* target_plac;
};
//typedef vector<road> plac;
struct queue_el{
	bool operator<(const queue_el& rhs) const{
		//if(t != rhs.t)
			return t > rhs.t;
		//if(current_plac->i != rhs.current_plac->i)
		//	return current_plac->i < rhs.current_plac->i;
		//if(current_plac->j != rhs.current_plac->j)
		//	return current_plac->j < rhs.current_plac->j;
	}
	int t;
	plac* current_plac;
};

int solve(int start_t, int y1, int x1, int y2, int x2, plac **place){
	//std::queue<queue_el> bfs_queue;
	std::priority_queue<queue_el> bfs_queue;
	queue_el initial_el({start_t,&place[y1][x1]});
	bfs_queue.push(initial_el);
	while(1){
		queue_el current_el = bfs_queue.top();
		bfs_queue.pop();
		//std::cout << current_el.t << " i:" << current_el.current_plac->i << " j:" << current_el.current_plac->j << "\n";
		current_el.current_plac->explored=true;
		if((current_el.current_plac->i == y2) && (current_el.current_plac->j == x2)){
			return current_el.t;
		}
		for(road current_road : current_el.current_plac->roads){
			//std::cout << "Checking road ";
			//for(int i=0; i<current_road.cycles_n; i++) std::cout << current_road.cycles[i];
			//std::cout << "\n";
			//std::cout << "target: "
			if(current_road.target_plac->explored) continue;
			int current_cycle = current_el.t % current_road.cycles_n;
			bool is_red = !current_road.cycles[current_cycle];
			//std::cout << "isred: " << is_red<<"\n";
			queue_el to_add_el({current_el.t+is_red, current_road.target_plac});
			bfs_queue.push(to_add_el);
		}
	}
}

int main(){
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	int roads_n, roads_m, questions;
	std::cin >> roads_n >> roads_m >> questions;
	plac **place = new plac*[roads_n+1];
	for(int i=0; i<roads_n+1; i++){
		place[i] = new plac[roads_m+1];
	}
	for(int i=0; i<roads_n+1; i++){
		for(int j=0; j<roads_m+1; j++){
			place[i][j].i = i;
			place[i][j].j = j;
			place[i][j].explored = false;
		}

	}

	for(int i=0; i<roads_n; i++){
		for(int j=0; j<roads_m; j++){
			//place[i][j].i = i;
			//place[i][j].j = j;
			std::string cycles;
			std::cin >> cycles;

			road road_up_down;
			road_up_down.cycles_n = cycles.size();
			for(int k=0; k<cycles.size(); k++){ //Up road
				road_up_down.cycles[k] = cycles[k]=='1';
			}
			road_up_down.target_plac = &place[i][j+1];
			place[i][j].roads.push_back(road_up_down);

			road_up_down.target_plac = &place[i][j];
			place[i][j+1].roads.push_back(road_up_down);

			road_up_down.target_plac = &place[i+1][j+1];
			place[i+1][j].roads.push_back(road_up_down);

			road_up_down.target_plac = &place[i+1][j];
			place[i+1][j+1].roads.push_back(road_up_down);

			road road_left_right;
			road_left_right.cycles_n = cycles.size();
			for(int k=0; k<cycles.size(); k++){ //Left right road
				road_left_right.cycles[k] = cycles[k]=='0'; //inverted
			}
			road_left_right.target_plac = &place[i+1][j];
			place[i][j].roads.push_back(road_left_right);

			road_left_right.target_plac = &place[i][j];
			place[i+1][j].roads.push_back(road_left_right);

			road_left_right.target_plac = &place[i][j+1];
			place[i+1][j+1].roads.push_back(road_left_right);

			road_left_right.target_plac = &place[i+1][j+1];
			place[i][j+1].roads.push_back(road_left_right);
		}
	}

	for(int q=0; q<questions; q++){
		int start_t, y1, x1, y2, x2;
		std::cin >> start_t >> y1 >> x1 >> y2 >> x2;
		std::cout << solve(start_t, y1, x1, y2, x2, place) << "\n";
		for(int i=0; i<roads_n+1; i++){
			for(int j=0; j<roads_m+1; j++){
				place[i][j].explored = false;
			}
		}
	}
}