UVA11573 Ocean Currents

对于一艘在一片巨大的水域上的船来说，水流可能非常危险，但如果仔细规划路线，它们也可以成为船只前往终点的动力。你的任务就是帮助规划路线。 在湖面上每个点都有一个水流方向，你可以选择向水流方向移动一个单位，不用花费能量，或是向其他方向移动一个单位，花费 $1$ 单位的能量。船只能向以下八个方向移动：东、南、西、北、东南、东北、西南、西北。船只不可以离开海面的边界。 你需要制定一个策略，以最少的能量消耗到达目的地。 给定两个整数 $n,m$ 和一个 $n\times m$ 的矩阵表示湖面。 有 $q$ 次询问，每次询问给出四个数 $r_s,c_s,r_d,c_d$，求从 $(r_s,c_s)$ 移动到 $(r_d,c_d)$ 至少需要多少点能量。 $1\le n,m\le 10^3,1\le q\le 50$。

湖面用一个矩形网格来表示，第一行包含两个整数 $r,c$，表示该网格的行数和列数，$r,c\le 1000$。 第 $2$ 到 第 $r+1$ 行，每行包含 $c$ 个在 $[0,7]$ 之间的整数字符，表示湖面。字符 $\texttt{0}$ 表示水流向北，字符 $\texttt{1}$ 表示向东北，$\texttt{2}$ 表示向东，依此类推，按顺时针方向排列。 具体方向如下所示（`*` 表示当前所在的位置）： ``` 7 0 1 \|/ 6-*-2 /|\ 5 4 3 ``` 第 $r+2$ 行包含一个整数 $n$，表示将要航行的次数，$n\le 50$。 接下来 $n$ 行，每行包含四个整数 $r_s,c_s,r_d,c_d$，表示一次从 $(r_s,c_s)$ 到 $(r_d,c_d)$ 的航行。湖面下标从 $1$ 开始。

对于每个询问，输出一行一个整数，表示至少需要的能量消耗。