この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/b2b22aa77ad6da118c3e
次：https://qiita.com/sano192/items/95ed7094ff71400a2dce
【目標】
・マス目問題について入力を二次元配列として受け取りできるようになる
・あるマスから上下左右に向かって行う処理を実装することができるようになる
【概要】
二次元の座標(=マス目)と壁、障害物の位置が与えられ、何らかの処理を行うという問題は頻出だ。慣れていないと実装に戸惑うかもしれないが、一度書けるようになってしまえば難しいところはない。この問題の実装解説は長めだが頑張って読んでほしい。
【方針】
(X,Y)のマスから上、下、右、左方向へ、壁に当たるまで何マス進めるか調べればよい。
実装は以下の手順で行う。
(1)与えられた文字列を二次元配列として受け取る
(2)マス(X,Y)から上、下、右、左方向へ壁に当たるまで進み、それぞれの方向について見えるマス(=壁に当たるまでに通ったマス)の個数をカウントする
(3)マス(X,Y)自身の分を見えるマスのカウントに足す(+1)
(4)見えるマスのカウント数を出力する
どのようにコードを書くかは【実装】を見ていこう。
【実装】
入力を受け取る。
まずH、W、X、Yの部分。
H,W,X,Y=map(int, input().split())
(1)与えられた文字列を二次元配列として受け取る
地図の情報を二次元座標として受け取る。
最終的には
grid[行番号][列番号]
でマス(行番号,列番号)が空白(=”.”)か障害物(=”#”)かを確認できるようにしたい。
入力例1を例に説明しよう。
「入力例1」
4 4 2 2
##..
...#
#.#.
.#.#
この情報をgridという二次元配列に格納する。
まずgridという空のリストを作る。
grid=[]
次にS1~SHを受け取る。
for i in range(H):
S=input()
S=list(S)
grid.append(S)
SはH個あるのでH回のループを回す。
さらにSをリストに分解するため、S=list(S)と書く。
(例えばSが"##.."だった場合、list(S)は[ "#” , ”#” , ”.” , ”." ]と1文字ずつ分解されたリストになる)
これをgridに追加することで二次元配列を作ることができる。
入力が完了するとgridの要素はどうなっているか、確認してみよう。
grid=[ ['#', '#', '.', '.'], ['.', '.', '.', '#'], ['#', '.', '#', '.'], ['.', '#', '.', '#'] ]
黒い番号が1つ目のインデックス番号=行番号
赤い番号が2つ目のインデックス番号=列番号
となっている。
例えば
(0行目,0列目)のマス=grid[0][0]=”#”
(2行目,1列目)のマス=grid[2][1]=”.”
のように確認できる。
注意点としてリストのインデックス番号は1ではなく0からはじまるため、入力で与えられるマス(X,Y)も行番号、列番号をひとつずらしてgrid[X-1][Y-1]を見なければならない。
((X=1,Y=1のとき、マス(1,1)はgrid[0][0]に相当する)
そのためあらかじめX、Yを-1しておく。
X-=1
Y-=1
(2)マス(X,Y)から上、下、右、左方向へ壁に当たるまで進み、それぞれの方向について見えるマス(=壁に当たるまでに通ったマス)の個数をカウントする
見えるマスの個数を格納する変数をansとしておこう。
ans=0
まず上向きから確認する。
マス(X,Y)から順に上方向にマスを見ていくということはマス(X-1,Y)、(X-2,Y)、(X-3,Y)...を確認していくということだ。ここはfor文でi=1,2,3...について、grid[X-i][Y]を順に確認していけば良い。
つまり
grid[X-i][Y]
について、
・壁の場合(=”#”)
その先のマスは見えないので上方向は終了
・それ以外の場合(=”.”)
見えるマスとしてカウント=ansを+1する
という処理を行う。
# 上
for i in range(1,H):
if 0<=X-i<H:
if grid[X-i][Y]=="#":
break
else:
ans+=1
「if 0<=X-i<H:」
この部分は行番号がマイナスにならないようにつけた条件だ。
例えば
X=1、i＝3
の時
grid[X-i][Y]=grid[1-3][Y]=grid[-2][Y]
となり、行番号がマイナス、つまりもとのマス目の範囲を飛び出してしまう。
そうならないようにX-iが0～Hに収まるよう条件を書いている。
ところでX-iがHより大きくなることはないのだからX-i<H部分は不要では？と思った人がいるかもしれない。実際
「if 0<=X:」
と書いても問題ない。
しかし後に下向きの処理を書く時、上向きとほとんど同じ処理なので上向きの処理をコピペする。そのとき
「if 0<=X-i<H:」
と書いておいた方が書き直す部分を減らせるためミスが少なくなる。
ここまで書けたら下、右、左はほぼコピペで済む。
# 下
for i in range(1,H):
if 0<=X+i<H:
if grid[X+i][Y]=="#":
break
else:
ans+=1
下向きは上向きのX-iがX+iになっただけ。
右、左もほぼ同じ。
# 左
for i in range(1,W):
if 0<=Y-i<W:
if grid[X][Y-i]=="#":
break
else:
ans+=1
# 右
for i in range(1,W):
if 0<=Y+i<W:
if grid[X][Y+i]=="#":
break
else:
ans+=1
XではなくYに-i、+iしている。
(3)マス(X,Y)自身の分を見えるマスのカウントに足す(+1)
問題文に(マス(X,Y) 自身を含む)とあるため、その分をansに足す。
ans+=1
(4)見えるマスのカウント数を出力する。
print(ans)
この問題は解説を読み、自分で実装すると以下のエラーが頻発した、という人が多いと思う。
IndexError: list index out of range
(インデックスのエラー：リストインデックスが範囲外です)
行番号、列番号が範囲を超えているというエラーだ。visual studio codeなどのコードエディタでステップ実行をしながら、どのタイミングでインデックス番号が範囲を超えているか確認し、コードを修正しよう。
【コード全文】
H,W,X,Y=map(int, input().split())
grid=[]
for i in range(H):
S=input()
S=list(S)
grid.append(S)
X-=1
Y-=1
ans=0
# 上
for i in range(1,H):
if 0<=X-i<H:
if grid[X-i][Y]=="#":
break
else:
ans+=1
# 下
for i in range(1,H):
if 0<=X+i<H:
if grid[X+i][Y]=="#":
break
else:
ans+=1
# 左
for i in range(1,W):
if 0<=Y-i<W:
if grid[X][Y-i]=="#":
break
else:
ans+=1
# 右
for i in range(1,W):
if 0<=Y+i<W:
if grid[X][Y+i]=="#":
break
else:
ans+=1
ans+=1
print(ans)
この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/b2b22aa77ad6da118c3e
次：https://qiita.com/sano192/items/95ed7094ff71400a2dce