【競技プログラミング】AtCoder Beginner Contest 359_C問題

# 問題
https://atcoder.jp/contests/abc359/tasks/abc359_c

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 解法手順1
## 解法アプローチ

タイルの配置は交互に変わるため、始点と終点の座標の偶奇性を考慮する。
最短経路は、まず垂直方向に移動し、その後水平方向に移動することで求められる。

## 解法手順

1. 入力として始点(Sx, Sy)と終点(Tx, Ty)の座標を受け取る。

2. 始点と終点がそれぞれどのタイルにあるかを判定する。これは座標の偶奇性を利用して行う。

3. 始点と終点を、それぞれのタイルの左端に調整する。これにより、水平方向の移動を簡単に計算できるようになる。

4. 水平方向の距離(a)と垂直方向の距離(b)を計算する。

5. もし水平距離が垂直距離以下の場合、答えは垂直距離に等しい。

6. 水平距離が垂直距離より大きい場合、垂直移動後に残りの水平距離の半分を追加で移動する必要がある。

7. 計算された最小の通行料を出力する。



# ACコード1
```python:ac.py
def io_func():
    # 始点の座標を入力として受け取る
    Sx, Sy = map(int, input().split())
    # 終点の座標を入力として受け取る
    Tx, Ty = map(int, input().split())
    return Sx, Sy, Tx, Ty

def solve(Sx, Sy, Tx, Ty):
    # 始点と終点のタイルの左端判定用リスト
    A = [1] * 2  # 初期値は1（右端）

    # 始点のタイル判定
    if (Sy % 2 == 0 and Sx % 2 == 0) or (Sy % 2 == 1 and Sx % 2 == 1):
        A[0] = 0  # 左端

    # 終点のタイル判定
    if (Ty % 2 == 0 and Tx % 2 == 0) or (Ty % 2 == 1 and Tx % 2 == 1):
        A[1] = 0  # 左端

    # 始点と終点を左端に調整
    Sx += 1 - A[0]
    Tx += 1 - A[1]

    # 始点が終点より右にある場合、座標を反転
    if Sx > Tx:
        Sx, Tx = -Sx, -Tx

    # 水平方向の距離を計算
    a = Tx - Sx
    # 垂直方向の距離を計算
    b = abs(Ty - Sy)

    # 最小の通行料を計算
    if a <= b:
        answer = b
    else:
        answer = b + (a - b) // 2

    return answer

# メイン処理
Sx, Sy, Tx, Ty = io_func()
result = solve(Sx, Sy, Tx, Ty)
print(result)

###
# Sx, Sy: 始点の座標
# Tx, Ty: 終点の座標
# A: 始点と終点のタイルが左端かどうかを示すリスト（0: 左端, 1: 右端）
# a: 水平方向の距離
# b: 垂直方向の距離
# answer: 最小の通行料

# 1. io_func関数で入力を受け取る
# 2. solve関数で以下の処理を行う:
#    a. 始点と終点のタイルの位置（左端か右端か）を判定
#    b. 始点と終点の座標を左端に調整
#    c. 始点が終点より右にある場合、座標を反転
#    d. 水平方向と垂直方向の距離を計算
#    e. 最小の通行料を計算
# 3. 計算結果を出力する


```
## オブジェクト指向版1
```python:ac_object.py
import logging
from abc import ABC, abstractmethod

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
    formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
    
    file_handler = logging.FileHandler('program_trace.log')
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

class InputReader(ABC):
    @abstractmethod
    def read_input(self):
        pass

class ConsoleInputReader(InputReader):
    def read_input(self):
        # 始点の座標を入力として受け取る
        Sx, Sy = map(int, input().split())
        # 終点の座標を入力として受け取る
        Tx, Ty = map(int, input().split())
        return Sx, Sy, Tx, Ty

class Coordinate:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class TileSolver:
    def __init__(self, debug_mode=False):
        self.logger = setup_logger(debug_mode)

    def solve(self, start: Coordinate, end: Coordinate):
        self.logger.debug(f"開始: 始点({start.x}, {start.y}), 終点({end.x}, {end.y})")

        # 始点と終点のタイルの左端判定
        start_left = self._is_left_tile(start)
        end_left = self._is_left_tile(end)
        self.logger.debug(f"タイル判定: 始点左端={start_left}, 終点左端={end_left}")

        # 始点と終点を左端に調整
        start.x += 1 - int(start_left)
        end.x += 1 - int(end_left)
        self.logger.debug(f"左端調整後: 始点({start.x}, {start.y}), 終点({end.x}, {end.y})")

        # 始点が終点より右にある場合、座標を反転
        if start.x > end.x:
            start.x, end.x = -start.x, -end.x
            self.logger.debug("座標反転実行")

        # 水平方向と垂直方向の距離を計算
        horizontal_distance = end.x - start.x
        vertical_distance = abs(end.y - start.y)
        self.logger.debug(f"距離計算: 水平={horizontal_distance}, 垂直={vertical_distance}")

        # 最小の通行料を計算
        if horizontal_distance <= vertical_distance:
            answer = vertical_distance
        else:
            answer = vertical_distance + (horizontal_distance - vertical_distance) // 2

        self.logger.debug(f"最小通行料計算結果: {answer}")
        return answer

    def _is_left_tile(self, coord: Coordinate):
        if (coord.y % 2 == 0 and coord.x % 2 == 0) or (coord.y % 2 == 1 and coord.x % 2 == 1):
            return 0
        else:
            return 1


class TileGame:
    def __init__(self, input_reader: InputReader, solver: TileSolver):
        self.input_reader = input_reader
        self.solver = solver

    def play(self):
        Sx, Sy, Tx, Ty = self.input_reader.read_input()
        start = Coordinate(Sx, Sy)
        end = Coordinate(Tx, Ty)
        result = self.solver.solve(start, end)
        print(result)

if __name__ == "__main__":
    debug_mode = False  # デバッグモードを有効にする場合はTrueに設定
    input_reader = ConsoleInputReader()
    solver = TileSolver(debug_mode)
    game = TileGame(input_reader, solver)
    game.play()

```

### オブジェクト図
![sequence_diagram.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/d1c72ae0-5738-6480-9d63-74dedbdf106e.png)


### オブジェクト指向版1で書くメリット
#### 拡張性と再利用性
```python:ac_object.py
class FileInputReader(InputReader):
    def __init__(self, filename):
        self.filename = filename

    def read_input(self):
        with open(self.filename, 'r') as file:
            Sx, Sy = map(int, file.readline().split())
            Tx, Ty = map(int, file.readline().split())
        return Sx, Sy, Tx, Ty

# メイン処理を以下のように変更
if __name__ == "__main__":
    debug_mode = True
    input_reader = FileInputReader('input.txt')  # ファイルから入力を読み込む
    path_solver = TileSolver(debug_mode)
    executor = ProgramExecutor(input_reader, path_solver)
    executor.execute()

```

#### テスト容易性
```python:ac_object.py
import unittest

class TestPathSolver(unittest.TestCase):
    def setUp(self):
        self.solver = TileSolver(debug_mode=True)

    def test_solve_same_point(self):
        start = Coordinate(0, 0)
        end = Coordinate(0, 0)
        result = self.solver.solve(start, end)
        self.assertEqual(result, 0)

    def test_solve_horizontal_movement(self):
        start = Coordinate(0, 0)
        end = Coordinate(4, 0)
        result = self.solver.solve(start, end)
        self.assertEqual(result, 2)

    def test_solve_vertical_movement(self):
        start = Coordinate(0, 0)
        end = Coordinate(0, 5)
        result = self.solver.solve(start, end)
        self.assertEqual(result, 5)

    def test_solve_diagonal_movement(self):
        start = Coordinate(0, 0)
        end = Coordinate(3, 3)
        result = self.solver.solve(start, end)
        self.assertEqual(result, 3)

    def test_solve_complex_movement(self):
        start = Coordinate(1, 1)
        end = Coordinate(5, 3)
        result = self.solver.solve(start, end)
        self.assertEqual(result, 3)

if __name__ == '__main__':
    unittest.main()
```