U241846 路线

> 路曼曼其修远兮。 小 $P$ 在一次模拟赛中 $AK$ 虐全场，他的好朋友夹道欢送向他表示祝贺。

小 $P$ 在学校参加了一场模拟赛，取得了不错的成绩。考完以后，他想从学校回家，但他的朋友们挤成了一团祝贺小 $P$ ，小 $P$ 不得不花费 $a_{i,j}$ 的时间和他们聊天。 但是小 $P$ 有一张 $n\times n$ 的地图，学校在地图上的 $(x, y)$ 点，他的家在 $(p,q)$ 点上，小 $P$ **只能在地图上进行水平或垂直运动，不能斜着走**。 现在小 $P$ 把那张地图给你，请你给小 $P$ 规划一条路线回家，要求时间尽量**少**。

**本题有多组测试数据**。 - 第一行输入一个正整数 $n$ ，表示地图的规格。 - 接下来 $n$ 行，每行 $n$ 个整数，分别表示从此处走小 $P$ 要和他的朋友聊天的时长。 - 第 $n+2$ 行输入 $4$ 个正整数，表示小 $P$ 学校的坐标和家的坐标，即题目中的 $(x,y)$ 和 $(p,q)$ 。

输出一个整数，表示小 $P$ 回家的最短时长。

### 数据范围与约定 数据范围： - $n\le 50$ ； - $0\le a_{i,j} \le 50$ ； - $x,y,p,q\le n$ 。 保证存在路线可以从学校回家，两个坐标均存在于地图内。 ### 提示 此题的做法： - 深度优先搜索 $DFS$ ； - 广度优先搜索 $BFS$ ； - 动态规划/递归 $DP$ 。 如需 $AC$ 程序，可以从附件下载。 ### 样例说明 |||| |:-:|:-:|:-:| |第 $1$ 步，取 $1$|第 $2$ 步，取 $2$|$3$| |$2$|第$3$ 步，取 $1$|$2$| |$1$|第 $4$ 步，取 $1$|第 $5$ 步，取 $0$| |||| 故结果为 $1+2+1+1+0=5$ 。