RIOI_2_3 - Path of the righteous man


 You are given N*N matrix A filled with integers, which represents map of country "What" ("What" ain't no country I ever heard of) . Our hero is called Brett. Brett has many enemies, namely Jules and Vincent (Jules doesn't like him because he said "what" too many times), but his biggest enemy is Marcellus Wallace, because Brett treated him like a male dog treats female dog. And Marcellus most certainly does not look like a female dog. 

But Brett cannot sit at home all day enjoying his Big Kahuna burgers, he has to go from cell (sx, sy) to cell (ex, ey).

From cell (x, y) Bret can go to (x+1, y), (x, y+1), (x-1, y), (x, y-1).

If A[x][y] = S, we say that this cell is property of mafia boss S. When Brett visits cell (x, y), and has not yet apologised to boss A[x][y], then he apologizes, after that he can visit any cell controlled by A[x][y] without apologizing. Brett does not like to apologise ( because there is always chance to hear Ezekiel 25 17 ), so he asks you to find him path which minimizes number of times he has to apologise.

You are given N*N matrix A filled with integers, which represents map of country "What" ("What" ain't no country I ever heard of) . Our hero is called Bret. Bret has many enemies, namely Jules and Vincent (Jules doesn't like him because he said "what" too many times), but his biggest enemy is Marcellus Wallace, because Bret treated him like male dog treats female dog. 

Bret has to go from cell (sx, sy) to cell (ex, ey).
From cell (x, y) Bret can go to (x+1, y), (x, y+1), (x-1, y), (x, y-1).
If A[x][y] = S, we say that this cell is property of mafia boss S. When Bret visits cell (x, y), and has not yet apologised to boss A[x][y], then he apologizes, after that he can visit any cell controlled by A[x][y] without apologizing. Bret does not like to apologise ( because there is always chance to hear Ezekiel 25 17 ), so he asks you to find him path which minimizes number of times he has to apologise.

Constranits: 

N <= 50

0 <= A[i][j] < 10

Input

First line contains number t donating number of testcases. First line of each testcase consists of number N. N lines followscontaining N numbers donating matrix A. After that two lines follow, containing sx, sy and ex, ey.

Output

For each test output number minimal number of times bret has to apologise.

Example

Input:
3
5
0 1 0 2 3
0 2 0 3 1
0 5 0 0 0
0 5 7 8 0
0 0 0 0 0
0 0
0 4 
5
0 1 0 2 3
0 2 0 3 1
0 5 0 0 0
0 5 7 8 0
0 0 0 0 0
0 0
0 2
5
0 1 0 8 3
0 2 0 3 1
0 5 0 0 0
0 5 7 8 9
0 0 0 0 0
0 0
0 3
Output:
3
1
2
Explanation of second test case : Bret can reach cell (0, 2) following path on which each cell is controled by boss 0.
NOTE : If you wish to understand references in problem statement, 
watch movie Pulp Fiction, or this clip http://www.youtube.com/watch?v=aBs3Mu-qous

hide comments
deepak_d14: 2017-08-30 22:06:19

AC in first go!!! use bfs+bitmasking and in last check the "on" state which have least no of ones!!

silent_lamp: 2017-05-27 19:19:37

@Buda M please explain the question ,its very hard to understand or else add a proper test case explaination :)

conquistador: 2017-04-02 20:11:13

i dare you , i double dare you to solve this problem .( pulp fiction reference );

vladimira: 2017-03-05 20:35:45

nice problem but time limits works for a few languages like c++, c. So much effort, writing my code in python. Dislike, sry. And link to youtube doesn't work. And desctiption is difficult to read.

vengatesh15: 2017-02-15 08:00:08

Finally removed from my todo_list after a 4 month.

singh1495: 2017-02-07 16:43:22

bfs + bitmasking nice question

auro32: 2017-02-07 11:02:53

bfs + bitmask == gg

Buda IM (retired): 2016-07-31 20:02:01

Added support for new languages such as C++14

enigmus: 2016-07-31 12:41:47

Very good problem, but maybe a little too tight time limit.
It would also be nice if you added C++11/C++14 support

mario_92: 2016-07-27 15:59:14

What should be the output for sx==ex and sy==ey?
Please provide some tougher test cases. My code is giving right output for all the test cases mentioned here but still it shows WA. If only I could know the test case for which it does not produce the desired output!

Last edit: 2016-07-27 16:23:47

Added by:Buda IM
Date:2012-11-01
Time limit:0.481s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC COBOL D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC PICO CHICKEN VB.NET
Resource:Own Problem