ABC197 B問題 Visibilityを解いて反省
ABC197 B問題 Visibilityを解いたのですが、思ったよりも時間がかかって反省しました。
縦 H 行、横 W 列のマス目があり、いくつかのマスには障害物が置かれています。
与えられた最初の位置から縦、横に見えるマスの数を答える問題です。
こういう迷路のような地図が与えられる問題はよくあって、今回はその中でもとても簡単な問題の部類です。
よくあるのですが、インデックスの数と座標の対応のとり方とか、上下の移動の仕方とか、慣れてないと今回の私のようにバグを埋め込んでしまって思ったよりも時間がかかるんだなと思いました。
解き方としては単純で開始の位置から障害物に当たるまで上下左右に探索してマスの数を数えます。
またこの問題は面白いことにXは上から何番目の行を表していて、Yは左から何番目の列を表しているんですよね。
これでまた私は混乱して無駄に時間を食ってしまいました。
慣れの問題だと思うんですけど、x軸は横軸、y軸は縦の軸なんて思い込んでると、余計に混乱します。
なので、変数名にrowのrを入れて、columnのcを入れて混乱を防ぎました。
最終的な私のコードはこんな感じです。
H, W, X, Y = map(int, input().split()) graph = [[s for s in input()] for _ in range(H)] s_x = X - 1 s_y = Y - 1 count = 1 p_r = s_x - 1 p_c = s_y # 上へ探索 while p_r >= 0 and graph[p_r][p_c] == '.': count += 1 p_r -= 1 p_r = s_x + 1 p_c = s_y # 下へ探索 while p_r < H and graph[p_r][p_c] == '.': count += 1 p_r += 1 p_r = s_x p_c = s_y - 1 # 左へ探索 while p_c >= 0 and graph[p_r][p_c] == '.': count += 1 p_c -= 1 p_r = s_x p_c = s_y + 1 # 右へ探索 while p_c < W and graph[p_r][p_c] == '.': count += 1 p_c += 1 print(count)
xとyの意味のこともあり、今コードだけ読んでも混乱します。
公式解説のコードはもっとシンプルでした。
私と大きく異なっているところとしては、探索方向によって初期位置は変更せずに、重複してカウントして、-3しているところです。
公式解説のコードを同じノリでpythonにするとこんな感じです。
H, W, X, Y = map(int, input().split()) graph = [[s for s in input()] for _ in range(H)] s_r = X - 1 s_c = Y - 1 # 最初の位置は重複して数えるので3引いておく count = -3 # 下へ探索 for i in range(s_r, H): if graph[i][s_c] != '.': break count += 1 # 上へ探索 for i in range(s_r, -1, -1): if graph[i][s_c] != '.': break count += 1 # 右へ探索 for i in range(s_c, W): if graph[s_r][i] != '.': break count += 1 # 左へ探索 for i in range(s_c, -1, -1): if graph[s_r][i] != '.': break count += 1 print(count)
こっちの方がわかりやすいですね。
慣れるようにもっと問題解いていこうと思います。