ABC184 C - Super Ryuma

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    r1, c1 = il()
    r2, c2 = il()
    d = abs(r1-r2)+abs(c1-c2)
    ret = 0
    if r1 == r2 and c1 == c2:
        # 同じ位置の場合
        ret = 0
    elif r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2 or d <= 3:
        # 1手で移動可能な場合
        ret = 1
    elif (r1 + c1 + r2 + c2) % 2 == 0:
        # 2手で移動可能な場合
        # (r1, c1), (r2, c2)の合計が2で割り切れる
        # つまり、スタートからゴールまで斜めの移動のみで到達可能
        ret = 2
    elif d <= 6:
        # 2手で移動可能な場合
        # |a-c|+|b-d| <= 3 を2回行って移動出来る範囲
        ret = 2
    elif abs((r1+c1) - (r2+c2)) <= 3:
        # 2手で移動可能な場合
        # 1手目
        # a+b = c+d
        # (a+b) - (c+d) = 0
        # 2手目
        # |a-c|+|b-d| <= 3
        # 移動範囲
        # (a+b) - (c+d) = 3
        ret = 2
    elif abs((r1-c1) - (r2-c2)) <= 3:
        # 2手で移動可能な場合
        # 1手目
        # a-b = c-d
        # (a-b) - (c-d) = 0
        # 2手目
        # |a-c|+|b-d| <= 3
        # 移動範囲
        # (a-b) - (c-d) = 3
        ret = 2
    else:
        # 全てのマスは3手以内に到達可能
        ret = 3
    print(ret)


if __name__ == '__main__':
    main()

考え方

アライグマ「ABC184のA,Bの原案、Dのwriterだったのだ！　C問題はいきなり難しいのだ。斜め移動を2回すると、r1+c1と偶奇が等しいマスにはどこにでも行けるから、答えは3以下になるのだ。0回1回で行けるかはすぐわかるから、2回で行けるかどうかが判定できればいいのだ」

— 競技プログラミングをするフレンズ (@kyopro_friends) November 22, 2020

フレンズ氏の解説tweet通り、
全てのマスには必ず3手以内で到達可能であるため、
あとは全てのケースを洗い出してケース分けを行う。

基本的には2手で到達可能なケースを全て洗い出すだけ。
（0手はスタート地点がゴール地点の場合、1手は指示された3つの移動条件で到達できるか判定するだけ）