Solution better than O(AB)?


#1

Here’s an O(1) for A>4, B>4.

    if (std::min(A, B) > 4) {
        int x = std::abs(C - E);
        int y = std::abs(D - F);
        if (x < y)
            std::swap(x, y);
        if (x <= 2 * y) {
            int steps = x + y;
            while (steps % 3 != 0)
                steps += 2;
            return steps / 3;
        }
        
        if (x == 1 && y == 0) return 3;
        int extra = (x - 2 * y) % 4;
        if (extra > 1) extra--;
        return x / 2 + extra;
    }

Note: For A=B=4, it doesn’t work for (1,1) -> (4,1) as we cannot do (1,1)->(3,2)->(5,3)->(4,1).

Is this algorithm correct? And any other thoughts for other cases? (i.e. for max(A, B) > 4 && min(A, B) <= 4)