SP12612 RIOI_2_3 - Path of the righteous man

在一个 $N \times N$ 的整数矩阵 $A$ 中，每个数字代表名为「What」的国家的地图（「What」这个名字可不是我听说过的任何国家）。主角布雷特有许多敌人，比如朱尔斯和文森特（因为布雷特说了太多次“what”），但他最大的敌人是马塞尔·华莱士，因为布雷特曾对他不敬。 布雷特不能一直待在家里享受他的汉堡，他需要从起始坐标 $(s_x, s_y)$ 移动到目标坐标 $(e_x, e_y)$。 从坐标 $(x, y)$ 出发，布雷特可以向上、下、左、右移动到相邻的格子，即可以到达 $(x+1, y)$、$(x, y+1)$、$(x-1, y)$ 和 $(x, y-1)$。 如果格子 $(x, y)$ 的值为 $A[x][y] = S$，表示该地盘属于老大 $S$。当布雷特首次拜访某个老大的地盘时，他必须先道歉。之后，只要他不离开该老大控制的区域，就无需再道歉。布雷特不喜欢道歉（因为这总是让他忍不住想起以西结书 25:17），所以他希望你能为他找到一条路径，使得他道歉的次数最少。

第一行是一个整数 $t$，表示测试用例的数量。对于每个测试用例，第一行是一个整数 $N$。接下来的 $N$ 行每行包含 $N$ 个整数，构成矩阵 $A$。紧接着是两行，分别表示起点坐标 $(s_x, s_y)$ 和终点坐标 $(e_x, e_y)$。

针对每个测试用例，输出布雷特最少需要道歉的次数。

1 ≤ $t$ ≤ 10,000 1 ≤ $N$ ≤ 100 1 ≤ $A[x][y]$ ≤ 1,000,000 1 ≤ $s_x, s_y, e_x, e_y$ ≤ $N$ **本翻译由 AI 自动生成**