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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct node_t
{
	char len=0;
	char v[9];

	int g=-1;
	unsigned int best_time=(unsigned int)-1;
};

int n,m,q;
vector<node_t> s;
node_t* endNode=nullptr;

void read_board()
{
	cin >> n >> m >> q;
	s.resize((n+1) * (m+1));
	string temp_string;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
		{
			cin >> temp_string;
			node_t& w = s[i * (m+1) + j];
			w.len = (char)temp_string.length();
			for (int k = 0; k < w.len; ++k)
				w.v[k] = temp_string[k];
			w.v[w.len] = 0;
		}
}

struct queue_entry_t
{
	int x;
	int y;

	bool operator<(const queue_entry_t& other) const
	{
		const int my_time=s[x+y*(m+1)].best_time;
		const int other_time=s[other.x+other.y*(m+1)].best_time;
		return my_time>other_time;
	}
};

int g;
vector<queue_entry_t> queue;

/*


2 2 7
01 1100
001 10
0 0 0 2 2
1 0 1 2 1
5 2 1 0 0
0 0 2 2 2
15 1 1 0 0
16 1 1 0 0
7 2 2 2 2

2 2 1
01 1100
001 10
7 2 2 2 2

*/

void visit(const queue_entry_t& curr_element, const node_t& src_node, int crossing_x_dir, int crossing_y_dir, int target_x_dir,int target_y_dir)
{
	const int crossing_x=curr_element.x+crossing_x_dir;
	const int crossing_y=curr_element.y+crossing_y_dir;
	if(crossing_x<0||crossing_x>=m||
		crossing_y<0||crossing_y>=n)
		return;
	node_t& crossing_node=s[crossing_x+crossing_y*(m+1)];

	const int target_x = curr_element.x+target_x_dir;
	const int target_y = curr_element.y+target_y_dir;
	node_t& target_node=s[target_x+target_y*(m+1)];

	int wait_time=0;
	const char expected_dir_char=target_x_dir?'1':'0';
	for(int i=0;i<crossing_node.len;++i)
	{
		if(crossing_node.v[(src_node.best_time+i)%crossing_node.len]==expected_dir_char)
			break;
		++wait_time;
	}
	
	const int new_time=src_node.best_time+wait_time;
	if(target_node.g==g&&target_node.best_time<=new_time)
		return;
	if(new_time>=endNode->best_time)
		return;
	target_node.best_time=new_time;
	target_node.g=g;

	const queue_entry_t new_entry{target_x,target_y};
	queue.push_back(new_entry);
	push_heap(queue.begin(),queue.end());
}

void solve(int t,int a,int b,int c,int d)
{
	if(a==c&&b==d)
	{
		cout<<t<<endl;
		return;
	}

	queue.clear();

	const queue_entry_t start_entry{a,b};
	queue.push_back(start_entry);
	s[a+b*(m+1)].best_time=t;
	s[a+b*(m+1)].g=g;

	endNode=&s[c+d*(m+1)];
	endNode->best_time=(unsigned int)-1;

	while(!queue.empty())
	{
		pop_heap(queue.begin(),queue.end());
		const queue_entry_t curr_entry = queue.back();
		queue.pop_back();

		const node_t& curr_node = s[curr_entry.x+curr_entry.y*(m+1)];

		visit(curr_entry,curr_node,-1,-1,-1,0);
		visit(curr_entry,curr_node,-1,-1,0,-1);
		
		visit(curr_entry,curr_node,-1,0,-1,0);
		visit(curr_entry,curr_node,-1,0,0,1);
		
		visit(curr_entry,curr_node,0,0,1,0);
		visit(curr_entry,curr_node,0,0,0,1);
		
		visit(curr_entry,curr_node,0,-1,0,-1);
		visit(curr_entry,curr_node,0,-1,1,0);
	}

	cout<<endNode->best_time<<endl;
}

int main()
{
	read_board();
	for(g=0;g<q;++g)
	{
		int t,a,b,c,d;
		cin>>t>>b>>a>>d>>c;
		solve(t,a,b,c,d);
	}
	return 0;
}