【競技プログラミング】AtCoder Beginner Contest 197_B問題

問題

要約

縦H行、横W列のマス目があり、一部のマスには障害物が置かれている。
マスの位置は上からi番目、左からj番目で(i, j)と表される。

マス目の状態はH個の文字列S1, S2, S3, ..., SHで与えられる。
Siのj文字目がマス(i, j)の状態を表し、'#'は障害物があること、'.'は障害物がないことを示す。

あるマスから別のマスが「見える」とは、以下の条件を満たす場合である

1. 2つのマスが同じ行または列にある
2. 2つのマスの間（両端のマスを含む）に障害物が1つもない

問題の目的は、指定されたマス(X, Y)から「見える」マスの数（マス(X, Y)自身を含む）を求めることである。

• H: マス目の行数
• W: マス目の列数
• Si: i行目のマス目の状態を表す文字列
• X, Y: 視点となるマスの座標

既存投稿一覧ページへのリンク

一覧ページ

解法手順

指定されたマス(X, Y)から上下左右の4方向に対して、障害物に当たるまでの「見える」マスを数えることで解決できる。
まず、マス(X, Y)自体が障害物でないかを確認し、その後、各方向に対して探索を行う。
探索は、マス目の範囲内にあり、かつ障害物に当たるまで続ける。

1. 入力を受け取り、マス目の状態を2次元リストとして保存する。
2. 上下左右の4方向を表す方向ベクトルを定義する。
3. マス目の範囲内かどうかをチェックする関数を定義する。
4. マス(X, Y)が障害物でない場合、カウントを1から開始する。障害物の場合は0から開始する。
5. 4方向それぞれに対して以下の処理を行う:
   a. 現在位置を(X, Y)に設定する。
   b. 現在位置から方向ベクトルに従って1マス進む。
   c. 新しい位置がマス目の範囲外なら、その方向の探索を終了する。
   d. 新しい位置が障害物なら、その方向の探索を終了する。
   e. 新しい位置が空きマスなら、カウントを1増やし、bに戻る。
6. 全ての方向の探索が終わったら、最終的なカウントを出力する。

ACコード

ac.py

# 標準入力の処理を行う関数
def io_func():
    # マス目の高さ、幅、指定されたマスの座標を入力として受け取る
    H, W, X, Y = map(int, input().split())
    # マス目の状態を2次元リストとして保存
    field = [[c for c in input()] for _ in range(H)]
    return H, W, X, Y, field

# 上下左右の4方向を表す方向ベクトル
d = [[0, -1], [-1, 0], [0, 1], [1, 0]]

# マス目の範囲内かどうかをチェックする関数
def check(x, y, h, w):
    # マス目の範囲外ならFalse、範囲内ならTrueを返す
    if x < 0 or x >= h or y < 0 or y >= w:
        return False
    return True

# 主な処理を行う関数
def solve(H, W, X, Y, field):
    # 指定されたマスが障害物でない場合、カウントを1から開始
    if field[X-1][Y-1] == '.':
        count = 1
    else:
        count = 0
    
    # 4方向それぞれに対して探索を行う
    for i in range(len(d)):
        x, y = X - 1, Y - 1  # 現在位置を(X, Y)に設定
        while True:
            # 現在位置から方向ベクトルに従って1マス進む
            x += d[i][0]
            y += d[i][1]
            # 新しい位置がマス目の範囲外なら、その方向の探索を終了
            if not check(x, y, H, W):
                break
            # 新しい位置が障害物なら、その方向の探索を終了
            if field[x][y] == '#':
                break
            # 新しい位置が空きマスなら、カウントを1増やす
            else:
                count += 1
    
    # 最終的なカウントを返す
    return count

# メイン処理
H, W, X, Y, field = io_func()  # 入力を受け取る
result = solve(H, W, X, Y, field)  # 解を計算
print(result)  # 結果を出力

###
# H: マス目の高さ
# W: マス目の幅
# X, Y: 指定されたマスの座標
# field: マス目の状態を表す2次元リスト
# d: 上下左右の4方向を表す方向ベクトル
# count: 「見える」マスの数をカウントする変数
# x, y: 探索中の現在位置

# 1. io_func関数: 標準入力から必要なデータを読み取り、返す
# 2. check関数: 与えられた座標がマス目の範囲内かどうかをチェックする
# 3. solve関数: 主な処理を行う
#    - 指定されたマスが障害物かどうかでカウントの初期値を決定
#    - 4方向それぞれに対して探索を行い、「見える」マスをカウント
#    - 最終的なカウントを返す
# 4. メイン処理:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して解を計算
#    - 結果を出力する

オブジェクト指向版1

ac.py

from abc import ABC, abstractmethod
from typing import List, Tuple

# 入力インターフェース
class InputInterface(ABC):
    @abstractmethod
    def get_input(self) -> Tuple[int, int, int, int, List[List[str]]]:
        pass

# 標準入力クラス
class StandardInput(InputInterface):
    def get_input(self) -> Tuple[int, int, int, int, List[List[str]]]:
        # マス目の高さ、幅、指定されたマスの座標を入力として受け取る
        H, W, X, Y = map(int, input().split())
        # マス目の状態を2次元リストとして保存
        field = [[c for c in input()] for _ in range(H)]
        return H, W, X, Y, field

# マス目クラス
class Grid:
    def __init__(self, height: int, width: int, field: List[List[str]]):
        self.height = height
        self.width = width
        self.field = field

    def is_within_bounds(self, x: int, y: int) -> bool:
        # マス目の範囲内かどうかをチェック
        return 0 <= x < self.height and 0 <= y < self.width

    def is_obstacle(self, x: int, y: int) -> bool:
        # 指定された位置が障害物かどうかをチェック
        return self.field[x][y] == '#'

# 方向クラス
class Direction:
    # 上下左右の4方向を表す方向ベクトル
    DIRECTIONS = [(0, -1), (-1, 0), (0, 1), (1, 0)]

    @staticmethod
    def get_all_directions():
        return Direction.DIRECTIONS

# 可視マス計算クラス
class VisibleSquareCounter:
    def __init__(self, grid: Grid):
        self.grid = grid

    def count_visible_squares(self, start_x: int, start_y: int) -> int:
        # 指定されたマスが障害物でない場合、カウントを1から開始
        count = 1 if not self.grid.is_obstacle(start_x-1, start_y-1) else 0
        
        # 4方向それぞれに対して探索を行う
        for dx, dy in Direction.get_all_directions():
            x, y = start_x - 1, start_y - 1  # 現在位置を(start_x, start_y)に設定
            while True:
                # 現在位置から方向ベクトルに従って1マス進む
                x, y = x + dx, y + dy
                # 新しい位置がマス目の範囲外か障害物なら、その方向の探索を終了
                if not self.grid.is_within_bounds(x, y) or self.grid.is_obstacle(x, y):
                    break
                # 新しい位置が空きマスなら、カウントを1増やす
                count += 1
        
        return count

# メイン処理クラス
class MainProcessor:
    def __init__(self, input_interface: InputInterface):
        self.input_interface = input_interface

    def process(self):
        # 入力を受け取る
        H, W, X, Y, field = self.input_interface.get_input()
        # Gridオブジェクトを作成
        grid = Grid(H, W, field)
        # VisibleSquareCounterオブジェクトを作成
        counter = VisibleSquareCounter(grid)
        # 可視マスの数を計算
        result = counter.count_visible_squares(X, Y)
        # 結果を出力
        print(result)

# メイン処理
if __name__ == "__main__":
    input_interface = StandardInput()
    processor = MainProcessor(input_interface)
    processor.process()