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), (x1, y), (x, y1).
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.
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=aBs3Muqous
hide comments
gsivaganesh26:
20181009 16:48:46
please kindly send the anser in my gmail id: gsivaganesh26@gmail.com 

gsivaganesh26:
20181009 16:48:04
can i get the answer for this problem ??


nadstratosfer:
20180501 19:50:25
Wow, as I was ready to bring out the CPP gimp, one observation pushed the original PyPy code past the green bar. Even raw Python flies now! I find myself one smilin' motherfucker. Cool problem. Last edit: 20180501 19:58:27 

Simes:
20180122 19:27:37
I expect everybody already figured out that the start and finish coordinates are actually given as y x, and not x y as stated. 

holmesherlock:
20180121 17:51:56
extremely beautiful question:::) 

deepak_d14:
20170830 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:
20170527 19:19:37
@Buda M please explain the question ,its very hard to understand or else add a proper test case explaination :) 

conquistador:
20170402 20:11:13
i dare you , i double dare you to solve this problem .( pulp fiction reference ); 

vladimira:
20170305 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:
20170215 08:00:08
Finally removed from my todo_list after a 4 month. 
Added by:  Buda IM 
Date:  20121101 
Time limit:  0.481s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC COBOL DDMD ELIXIR FANTOM GOSU GRV JSMONKEY NIM OBJC PICO CHICKEN VB.NET 
Resource:  Own Problem 