Fast Robot

Level 4
Fast robot
Mr. Noh is responsible for enhancing the movement of a robot faster.
Now, Mr. Noh is thinking like this: The speed of the robot decreases when it changes its direction.
Therefore, it requires a study of the acceleration in direction changes.
However, the better method than that is to use the route with the minimum number of direction changes when it moves from point A to point B.


Because of that, he studies a maze.
When the maze information is given, he tries to create a program to move it from the starting point to the arriving point based on the minimized direction changes.


Let’s find out the minimum direction changes possible from the starting point to the arriving point when the maze information is given.


Time limit : 1 sec (Java : 2 sec)


[Input]
There can be more than one test case in the input file. The first line has T, the number of test cases.
Then the totally T test cases are provided in the following lines (T ≤ 10 )
In each test case, The width and height of the maze are given as N & M separately at the first row. (1 ≤ N, M ≤ 200)
The horizontal coordinate and vertical coordinate of the starting point, and the horizontal coordinate and vertical coordinate of the arriving point are given separately in order at the second row.
Information of the maze is given from the third row the number (N). At this time, the path indicates 0; the wall indicates 1. There is no blank each other.


[Output]
In case of being reachable from the starting point to the arriving point, generate the minimum direction change frequency between two points.
If not, generate "-1"


[I/O Example]

Input

2
7 7
1 2 7 5
1111111
0000011
1011001
1011100
1011110
1000000
1111111
7 7
1 2 7 6
1111111
0000001
1011000
1011100
1011110
1000000
1111111


Output

3
2

4
8
7
10
265
3
1
2
-1
10
Time: 0.110000000 sec

#include <iostream>
#include <time.h>
using namespace std;

int oo = 2000000000;

int T, n, m, result;
char mp[201][201];
int xx1, yy1, xx2, yy2;

bool vs[201][201];
int cnt[201][201];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

int arr[160001][3];
int head, tail;

void init(){
	head = 0, tail = 0;
}

void push(int x, int y, int dir){
	arr[tail][0] = x, arr[tail][1] = y, arr[tail++][2] = dir ;
}

void pop(){ head++; }

bool isEmpty(){ return head == tail; }

int getX(){ return arr[head][0]; }

int getY(){ return arr[head][1]; }

int getD(){ return arr[head][2]; }

// 0:left, 1:right, 2:down, 3:up
void bfs(){
	init();
	
	push(xx1, yy1, -1);
	cnt[xx1][yy1] = 0;
	vs[xx1][yy1] = true;
	
	while(!isEmpty()){
		int x = getX();
		int y = getY();
		int d = getD();

		pop();

		if(x == xx2 && y == yy2){
			break;
		}
		 
		for(int dir = 0; dir < 4; dir++){
			int xx = x + dx[dir];
			int yy = y + dy[dir];
			while(xx >= 1 && xx <= n && yy >= 1 && yy <= m 
				&& mp[xx][yy] == '0' && !vs[xx][yy]){
				if(d == -1 || dir == d) cnt[xx][yy] = cnt[x][y];
				else if(dir != d) cnt[xx][yy] = cnt[x][y]+1;
				vs[xx][yy] = true;
				push(xx, yy, dir);
				xx += dx[dir];
				yy += dy[dir];
			}
		}

	}
}

int main(){
	freopen("input.txt", "r", stdin);

	// Calc clock
	
	clock_t time_start, time_end; 
	time_start = clock(); 
	

	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		// Input
		cin >> m >> n;
		cin >> yy1 >> xx1 >> yy2 >> xx2;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				cin >> mp[i][j];
				vs[i][j] = false;
			}
		}
		

		// Solve Problem
		bfs();

		// Output
		if(!vs[xx2][yy2]) cout << -1 << endl;
		else cout << cnt[xx2][yy2] << endl;
	}

	// Calc Time
	
	time_end = clock();
	cout.setf(ios::fixed);
	cout.precision(9);
	cout << "Time: "  
		<< double (time_end - time_start) / double (CLOCKS_PER_SEC) << " sec " << endl;
	
	return 0;
 }