方針

1手目を固定し、2手目と3手目の2手をまとめて考察します。

その2手について以下のように場合分けします。

1. 同じマスに戻ってくる場合

2手目に移動するマスが何通りあるかは下記のように \(O(1)\) で求めることができます。

それぞれの方向において移動できる場所がいくつあるかを数えます。例えば、縦方向であれば今いる場所以外の \(R-1\) 通り、横方向であれば \(C-1\) 通りです。1手目移動後時点でのマスを \((y, x)\) として、斜め方向は以下のようになります。

右下方向

\(R, C\) ともに増加方向です。右と下にいくつ移動できるかの \(\min\) をとればよいです。\(\min(R - y, C - x)\) となります。

左下方向

\(R\) 増加、\(C\) 減少の方向です。\(\min(R - y, x - 1)\) となります。

右上方向

\(R\) 減少、\(C\) 増加の方向です。\(\min(y - 1, C - x)\) となります。

左上方向

\(R, C\) ともに減少方向です。\(\min(y - 1, x-1)\) となります。

これら6つの和が求めたいものです。

2. 上記以外で同じ方向に移動する場合

同じマスに戻ってくる場合と比較すると、方向が、縦方向・横方向・右上左下方向・右下左上方向のうち、1つだけになります。

また、一手で \((r_t, c_t)\) に移動するものを省く必要があります。

よって、同じマスに戻ってくる場合の答えを \(-1\) すれば求めるものになります。

3. 上記以外

2手目3手目の方向を指定すると、2手目のマスは高々 \(1\) 通りになります。連立方程式を立てて解くことでその \(1\) 通りの候補を導くことができます。その候補のマスが存在するかどうかを判定すればよいです。

連立方程式の立式と求解

同じマスに戻ってくる場合以外について、2手目3手目の方向を指定し、連立方程式を立てることを考えます。 \(d_{y,k_1}, d_{x,k_1}, d_{y,k_2}, d_{x,k_2}\) は、方向を表すパラメータ (実装例の通り) であり、固定されています。その方向にどれだけ進んだかを表すパラメータ \(i, j\) を用いると、2手目の移動先から以下が成り立ちます。

\[ \left\{ \begin{array}{l} \displaystyle y + d_{y,k_1} i = r_t - d_{y,k_2} j \;\;\: \\ x + d_{x,k_1} i = c_t - d_{x,k_2} j \end{array} \right. \]

これを変形して行列に置き換えると以下のようになります。

\[ \begin{pmatrix} d_{y,k_1} & d_{y,k_2} \\ d_{x,k_1} & d_{x,k_2} \\ \end{pmatrix} \begin{pmatrix} i \\ j \\ \end{pmatrix} = \begin{pmatrix} r_t - y \\ c_t - x \\ \end{pmatrix} \]

\(i, j\) を求めることで、2手目の移動先がわかります。\(i, j\) が複数ある場合が、2手目3手目で同じ方向に移動する場合であり、それは逆行列が存在しない場合です。つまり行列式が \(0\) のとき、同じ方向に移動するだけでは到達できない場合を省くことで、上記2. の考察方針で実装できます。

行列式が \(0\) でない場合、逆行列が存在し、以下のように \(i, j\) を直接求めることができます。

\[ \begin{pmatrix} i \\ j \\ \end{pmatrix} = \frac{1}{d_{y,k_1} d_{x,k_2} - d_{x,k_1} d_{y,k_2}} \begin{pmatrix} d_{x,k_2} & -d_{y,k_2} \\ -d_{x,k_1} & d_{y,k_1} \\ \end{pmatrix} \begin{pmatrix} r_t - y \\ c_t - x \\ \end{pmatrix} \]

実装例

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)

int dy[4] = {0, 1, 1, 1};
int dx[4] = {1, -1, 0, 1};
int r, c, rs, cs, rt, ct;

int two(int y, int x) {
    int ret = 0;
    if(y == rt and x == ct) { // 同じ場所に戻ってくる
        ret += min(r - y, c - x) + min(y - 1, x - 1); // ななめ1
        ret += min(r - y, x - 1) + min(y - 1, c - x); // ななめ2
        ret += (r - 1) + (c - 1); // 縦と横
        return ret;
    }

    // 行列での立式上簡単のため
    int vy = rt - y;
    int vx = ct - x;

    rep(k1, 4) rep(k2, 4) {
        int D = dy[k1] * dx[k2] - dx[k1] * dy[k2]; // 行列式
        if(D == 0) { // 方向同じ
            if(vy * dx[k1] != vx * dy[k1]) continue;

            if(k1 == 3) ret += min(r - y, c - x) + min(y - 1, x - 1);  // ななめ1
            else if(k1 == 2) ret += (r - 1);  // 縦
            else if(k1 == 1) ret += min(r - y, x - 1) + min(y - 1, c - x); // ななめ2
            else ret += (c - 1); // 横
            ret --; 
        } else { // 逆行列
            int i =   dx[k2] * vy - dy[k2] * vx;
            int j = - dx[k1] * vy + dy[k1] * vx;
            if(i % D || j % D || i == 0 || j == 0) continue;
            i /= D; j /= D;

            // 2手目
            int Y = y + dy[k1] * i; 
            int X = x + dx[k1] * i;
            if(Y <= 0 || Y > r || X <= 0 || X > c) continue;
            ret ++;
        }
    }
    return ret;
}

int main() {
    cin >> r >> c >> rs >> cs >> rt >> ct;
    long long ans = 0;
    rep(k, 4) {
        for(int i = -100000; i <= 100000; i ++) {
            if(i == 0) continue;
            // 一手目固定
            int y = rs + dy[k] * i;
            int x = cs + dx[k] * i;
            if(y <= 0 || y > r || x <= 0 || x > c) continue;
            ans += two(y, x);
        }
    }
    cout << ans << endl;
    return 0;
}