AtCoder-ABC197 A - Rotate / B - Visibility【Python解答例】

AtCoder Beginner Contest197のA とB問題についてPythonの解答例を記事にしていきます。
atcoder.jp

AtCoder Beginner Contest197 A - Rotate

A - Rotate

問題文

長さ 3 の文字列 S が与えられます。
S の先頭の文字を S の末尾に移動して得られる文字列 S′ を出力してください。

制約

・S は英小文字のみからなる長さ 3 の文字列である

解答例

S = input()

ans = S[1] + S[2] + S[0]

print(ans)

解説

問題文のように与えられた3文字の文字列の先頭を末尾に移動させた文字列を答える問題です。

入力をSで受け取った後、Sの2文字目、3文字目、1文字目の順番でans変数に代入します。

そしてans変数を出力すればACでした。

AtCoder Beginner Contest197 B - Visibility

B - Visibility

問題文

縦 H 行、横 W 列のマス目があり、いくつかのマスには障害物が置かれています。
上から i 番目、左から j 番目のマスをマス (i,j) と表すことにします。
H 個の文字列 S1,S2,S3,…,SH が与えられます。
Si の j 文字目はマス (i,j) の状態を表し、# なら障害物が置かれていることを、. なら障害物が置かれていないことを表します。
このマス目上のあるマスからあるマスが見えるとは、2 つのマスが同じ行または列にあり、2 つのマスの間 (2 つのマス自身を含む) に障害物が 1 つも置かれていないことを意味します。
このマス目上のマスであって、マス目 (X,Y) から見えるもの (マス (X,Y) 自身を含む) の数を求めてください。

制約

・1≤H≤100
・1≤W≤100
・1≤X≤H
・1≤Y≤W
・Si は . および # のみからなる長さ W の文字列
・マス (X,Y) に障害物は置かれていない

解答例

h, w, x, y = map(int,input().split())
x -= 1
y -= 1

S = []
for i in range(h):
    S.append(input())

# 座標(x,y)自身もカウントするので初期値は1
ans = 1

# 座標(x,y+1)から下方向の探索
for i in range(1,101):
    if y+i >= w or S[x][y+i] == "#":
        break
    if S[x][y+i] != "#":
        ans += 1

# 座標(x,y-1)から上方向の探索
for i in range(1,101):
    if y-i < 0 or S[x][y-i] == "#":
        break
    if S[x][y-i] != "#":
        ans += 1

# 座標(x+1,y)から右方向の探索
for j in range(1,101):
    if x+j >= h or S[x+j][y] == "#":
        break
    if S[x+j][y] != "#":
        ans += 1

# 座標(x-1,y)から左方向の探索
for j in range(1,101):
    if x-j < 0 or S[x-j][y] == "#":
        break
    if S[x-j][y] != "#":
        ans += 1

print(ans)

解説

縦H行、横W列のマス目があり、マス目(x,y)から同じ行か同じ列で、間に障害物がないマス目の数を答える問題です。

問題文のようにマス目(x,y)から縦横4方向に探索しました。
求める数はans変数とし、座標(x,y)自身もカウントするので初期値は1にしました。
それぞれの探索はH行W列の範囲外に出るか、障害物にあたるまでansを1だけ足し続けていきます。

それぞれの4方向の探索が終わった後にansを出力すればOKです。

続いてABC197のC問題も記事にしていきたいと思います。

ABC197の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

【AtCoder版！蟻本】ARC 005 C - 器物損壊！高橋君【幅優先探索】

AtCoder版！蟻本の幅優先探索で類題としてあげられているAtCoder Regular Contest 005 C - 器物損壊！高橋君をPythonで解いていきます。

リンク

C - 器物損壊！高橋君

AtCoder Regular Contest 005 C - 器物損壊！高橋君

問題文

良く見てみるとカードの有効期限が切れていたので、高橋君は諦めて魚屋に直接うなぎを買いに行くことにしました。
　彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
　しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を 2 回までなら壊して道にすることができます。

　高橋君が魚屋に辿り着くことができるかどうか答えてください。

入力

・入力は H+1 行ある。
・1 行目は、街の南北の長さとして整数 H(1≦H≦500) と東西の長さとして整数 W(1≦W≦500) が空白で区切られて与えられる。
・2 行目からの H 行には、格子状の街の各区画における状態 c(i,j)(0≦i≦H−1, 0≦j≦W−1) が与えられる。
・i 行目 j 文字目の文字 c(i,j) はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。
・s : その区画が家であることを表す。
・g : その区画が魚屋であることを表す。
・. : その区画が道であることを表す。
・# : その区画が塀であることを表す。
・高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
・与えられた街の外を通ることはできない。
・s と g はそれぞれ 1 つずつ与えられる。

解答例

from collections import deque

# 入力
h, w = map(int,input().split())
maze = []   # 迷路の文字配列
for _ in range(h):
    maze.append(input())

# スタート、ゴールの探索
for y in range(h):
    for x in range(w):
        if maze[y][x] == "s": # スタート座標はsx,sy
            sx = x
            sy = y
        if maze[y][x] == "g": # ゴール座標はgx,gy
            gx = x
            gy = y

# scoreは各座標へ到達するまでに壊す必要のある壁の数（INFで初期化）
INF = int(1e9)
score = [[INF] * w for _ in range(h)]

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]


# スタートからゴールへのscoreを求めるbfs
def bfs():
    que = deque()
    que.append([sy,sx]) # スタート地点をキューに入れる
    score[sy][sx] = 0 # スタート地点のscoreを0とする

    # キューが空になるまで探索
    while len(que) != 0:
        p = que.popleft() # キューの先頭から取り出す
        if p[0] == gy and p[1] == gx: # ゴールなら探索終了
            break
        for i in range(4): # pから4方向に移動 移動後の点は(nx,ny)
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            # 移動先が迷路外ならスキップ
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            # 移動先が壁で未到達ならqueの後ろにpush
            if maze[ny][nx] == "#" and score[ny][nx] == INF:
                # scoreは+1
                score[ny][nx] = score[p[0]][p[1]] + 1
                que.append([ny,nx])
            # 移動先が壁でなく未到達ならqueの先頭にpush
            if maze[ny][nx] != "#" and score[ny][nx] == INF:
                # scoreはpと同じ
                score[ny][nx] = score[p[0]][p[1]]
                que.appendleft([ny,nx])

    return score[gy][gx]

res = bfs()
if res <= 2:
    print("YES")
else:
    print("NO")

解説

これまでの幅優先探索の問題のようにスタート地点からゴール地点に向かってBFSを行う問題です。
違う点は最短距離を求めるのでなく、壁を2回まで壊してゴールに到着できるかを答える問題です。

今回も迷路と同じ範囲の配列scoreを作成しますが、最短距離でなく壊した壁の数を記録していきます。

bfsではスタート地点をキューに入れて探索を始めます。
探索先が道と壁の場合で、キューの入れ方を変えました。
探索先が道の場合、探索元と同じscoreを記録してキューの先頭に入れます。
壁の場合は、探索元のscoreに+1した数を記録してキューの最後尾に入れました。

キューから先頭からしか取り出さないので、最初は壁を壊さずに行くことができるすべての道に到達するまで探索を続けます。

道の探索が終われば次はscoreが1の壁の探索です。
このとき、また道に出ればscore1として道の探索を行いました。
未探索の壁があればscoreをさらに＋1してキューの最後尾に入れます。

このような探索を繰り返していけば、最終的にはゴールまで探索が進み 壊した壁の数がscoreに記録されています。

問題にあわせてscoreが2以下ならYes、それより大きければNoを出力すればＯＫでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

Pythonで解く！初中級者が解くべき過去問精選 100 問 まとめ

AtCoderの学習のためこちらの記事で紹介されている初中級者が解くべき過去問精選100 問に取り組みました。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita

問題数が多いため分野ごとに分けて記載した記事を紹介します。

目次

作成中の記事ばかりですが地道に取り組んで更新していきます m(_ _)m

全探索：全列挙

ebisuke33.hatenablog.com

全探索：工夫して通り数を減らす全列挙

ebisuke33.hatenablog.com

全探索：ビット全探索

ebisuke33.hatenablog.com

全探索：順列全探索

ebisuke33.hatenablog.com

二分探索

ebisuke33.hatenablog.com

深さ優先探索（以下作成中です m(_ _)m）

幅優先探索

動的計画法：ナップザック DP

動的計画法：区間 DP

動的計画法：bit DP

動的計画法：その他

最短経路問題：ダイクストラ法

最短経路問題：ワーシャルフロイド法

最小全域木問題

高速な素数判定法

高速なべき乗計算

逆元を使う問題

累積和

Union-Find

その他のテクニック

実装問題

数学的な問題

蟻本の類題も解いていますので興味があればこちらもおすすめです。
ebisuke33.hatenablog.com

AtCoder-ABC196 D - Hanjo【Python解答例】

AtCoder Beginner Contest196のD - HanjoについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 196 - AtCoder

AtCoder Beginner Contest196 D - Hanjo

D - Hanjo

問題文

縦 H メートル、横 W メートルの長方形の部屋があります。
この部屋に 2 メートル × 1 メートルの区別できない畳 (長方形のタイル) A 枚と、1 メートル × 1 メートルの区別できない半畳 (正方形のタイル) B 枚を敷き詰めます。
2 メートル × 1 メートルの畳は縦長にも横長にも使うことができます。
敷き詰める方法は何通りあるでしょうか？
なお、2A+B=HW であることが保証されます。 また、回転や反転を行うことで初めて一致するような敷き詰め方は区別します。

制約

・入力は全て整数
・1≤H,W
・HW≤16
・0≤A,B
・2A+B=HW

解答例

h, w, a, b = map(int,input().split())

used = [[0]*w for _ in range(h)] # 畳があるか管理

res = 0

# マス(1,1)から(1,w)、(2,1)から(2,w)・・・(h,1)から(h,w)の順にdfs
def dfs(i,j,a,b):
    global res
    if a<0 or b<0:  # 畳がa枚以下やb枚以下になれば失敗
        return
    if j == w:      # 右端に来たら次の行へ
        j = 0
        i += 1
    if i == h:      # iがhになれば成功(条件にあう畳の敷き詰め方)
        res += 1
        return
    if used[i][j] == 1: # 調べるマスに畳があれば次のマスに
        return dfs(i,j+1,a,b)

    used[i][j] = 1
    dfs(i,j+1,a,b-1)    # 半畳 使う場合
    if j+1 < w and used[i][j+1] == 0:    #横に1畳置く場合
        used[i][j+1] = 1
        dfs(i,j+1,a-1,b)
        used[i][j+1] = 0

    if i+1 < h and used[i+1][j] == 0:   #縦に1畳置く場合
        used[i+1][j] = 1
        dfs(i,j+1,a-1,b)
        used[i+1][j] = 0

    used[i][j] = 0  # 元に戻す
    return res

print(dfs(0,0,a,b))

解説

縦H、横Wの部屋において、1畳(2マス分)の畳をA枚と、半畳(1マス分)の畳をB枚の敷き詰め方が何通りあるか答える問題です。

公式解説動画のようにDFSを用いた解法になります。

DFSでは左上マス(1,1)から(1,w)、(2,1)から(2,w)・・・(h,1)から(h,w)のように横書き文章の順に進めていきました。

関数では終了条件から書いています。
ひとつ目の終了条件は畳の枚数aやbがマイナスになれば終了しています。
畳を使いすぎれば失敗です。
2つ目は終了条件ではないですが、右端のマスを探索した後に次の行に移る動きをさせています。
3つ目は途中で畳が足りなくなったりしないで全マス探索し終えたことになるので、求める置き方ができたことになります。
したがってresに1を足しました。
4つ目は今、探索しているマスにすでに畳が置かれている状態なので、なにもしないで次のマスに移ります。

次からは遷移の部分です。
まず、現在のマスに畳を置かれたことをusedリストに記録します。
そこから3通りに分岐します。
・半畳の畳を置く場合
半畳の畳はどこでもおけるので、次のマス目に移動し半畳の畳を1枚引いて再度DFSします。

・1畳の畳を横に置く場合
現在のマスの右横に畳をおけるなら探索します。
右横のマスに畳を置いたことをusedにメモして、次のマス目から1畳の畳を1枚引いて再度DFSしました。
このDFS関数から戻ったとき、以降の探索のため右横の畳は消しておきます。

・1畳の畳を縦に置く場合
同じように現在のマスの下に畳をおけるなら探索します。
同様に下マスに畳を置いたことをusedにメモし、次のマス目から1畳の畳を1枚引いて再度DFSです。
このDFS関数から戻ったときも、下の畳は消しておきました。

このDFSによりi == hとなった数を数えることで、畳の敷き詰め方がわかります。
最後にresを出力すればOKでした。

ABC196の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC196 C - Doubled【Python解答例】

AtCoder Beginner Contest196のC - DoubledについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 196 - AtCoder

AtCoder Beginner Contest196 C - Doubled

C - Doubled

問題文

整数 N が与えられます。以下の条件を満たす 1 以上 N 以下の整数 x は何個あるでしょうか？
・x の十進表記 (先頭に 0 を付けない) は偶数桁であり、その前半と後半は文字列として等しい。

制約

・N は整数
・1≤N<10^12

解答例

N = input()
n = int(N)

digit = pow(10,len(N)//2)  # 入力Nの半分の桁

ans = 0
for i in range(1,digit):
    tmp = str(i)  # tmpを前半部分とする
    target = int(tmp + tmp)  # 偶数桁で前半と後半文字列が等しい数target
    if target <= n:
        ans += 1

print(ans)

解説

1以上N以下の数字において、偶数桁で前半と後半の文字列が等しい数の個数を答える問題です。

Nの制約が10^12までなので全探索では間に合いません。
したがって、前半部分（後半でもいいですが）にしぼって考えていきます。

入力Nの半分の桁をdigit変数に代入し、1からdigitまでのループを回します。
ループ値のがiのとき、まずiをstring型にしてtmpとします。
調べる値targetはtmp+tmpを再度int型にした値です。
これでtargetは偶数桁で前半と後半が等しい条件を満たす値になります。
targetがN以下ならans変数に1を足していきます。

ループを抜けてansを出力すればOKでした。

D問題はコンテスト中に解けませんでしたが、復習して記事にしたいと思います。

ABC196の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC196 A - Difference Max / B - Round Down【Python解答例】

AtCoder Beginner Contest196のA とBについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 196 - AtCoder

AtCoder Beginner Contest196 A - Difference Max

A - Difference Max

問題文

整数 a,b,c,d が与えられます。
a≤x≤b, c≤y≤d となるように整数 x,y を選ぶとき、 x−y の最大値を求めてください。

制約

・入力は全て整数
・−100≤a≤b≤100
・−100≤c≤d≤100

解答例

a, b = map(int,input().split())
c, d = map(int,input().split())

ans = b - c
print(ans)

解説

問題文のようにa≤x≤b, c≤y≤d となる整数 x,y を選び、 x−y の最大値を答える問題です。

x - yは最も大きいxから最も小さいyを引けば最大値になります。
a≤x≤bから最も大きいxはb、c≤y≤dから最も小さいyはcなのでb - cの値を出力すればACでした。

AtCoder Beginner Contest196 B - Round Down

B - Round Down

問題文

整数または小数 X が与えられるので、小数点以下を切り捨てて整数で出力してください。

制約

・0≤X≤10^100
・X は整数、または小数点以下が 100 桁以下の小数であり、先頭に余計な 0 は付かない

解答例

x = input()

ans = ""

for i in range(len(x)):
    if x[i] == '.':
        break
    else:
        ans += x[i]
print(ans)

解説

与えられたXについて、小数点以下を切り捨てた整数を答える問題です。

Xが10の100乗なので直接Xをint型で受け取っても誤差が大きすぎてWAになります。
したがって、入力はstringで受け取って、小数点が来るまでの値を出力しました。
for文で一文字目から調べていき、小数点でなければansに追加、小数点が来たら探索を終了します。

ループを抜けたあとでansを出力すればACでした。

続いてABC196のC問題も記事にしていきたいと思います。

ABC196の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

【AtCoder版！蟻本】AGC 033 A - Darker and Darker【幅優先探索】

AtCoder版！蟻本の幅優先探索で類題としてあげられているAGC 033 AをPythonで解いていきます。

リンク

A - Darker and Darker

AtCoder Grand Contest 033 A - Darker and Darker

問題文

縦 H 行、横 W 列の白黒に塗られたマス目が与えられます。 マス目の状態は A11 から AHW の HW 個の文字で表されており、 上から i 行目、左から j 列目にあるマスが黒色のとき Aij は #、 上から i 行目、左から j 列目にあるマスが白色のとき Aij は . となっています。
すべてのマスが黒色になるまで、以下の操作を繰り返し行います。
・辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
何回の操作を行うことになるか求めてください。 ただし、最初に与えられるマス目には少なくとも 1 つ黒色のマスが存在します。

制約

・1≦H,W≦1000
・Aij は # または .
・与えられるマス目には少なくとも 1 つ黒色のマスが存在する。

解答例

from collections import deque

h, w = map(int,input().split())

A = [] # マス目の文字配列
for i in range(h):
    A.append(list(input()))

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# 白マスをすべて黒マスに変える回数を調べるbfs
def bfs():
    que = deque()
    # すべての黒マス座標をqueにいれる
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                que.append([i,j])
    # 操作回数
    res = 0

    # キューが空になるまで探索
    while True:
        num = len(que)
        while num > 0:          # 操作回数ごとの要素を取り出す
            p = que.popleft()   # 先入れのキューの要素を取り出す
            for i in range(4):  # pから4方向に移動 移動後のマス目は(nx,ny)
                ny = p[0] + dy[i]
                nx = p[1] + dx[i]
                # 隣接するマス目が範囲内で白色かの判定
                if 0 <= nx < w and 0 <= ny < h and A[ny][nx] == ".":
                    A[ny][nx] = "#"     # 隣接する白マスを黒に置き換え
                    que.append([ny,nx]) # 隣接する白マスをqueにいれる
            num -= 1
        if len(que) == 0:
            break
        res += 1 # 操作回数を1増やす
    return res

print(bfs())

解説

H行、W列の白か黒に塗られたマス目があり、操作1回ごとに黒マスに隣接した白マスが黒マスに変わります。
すべてのマスが黒色に変わるために必要な操作回数を答える問題です。

先入れ先出しで探索できる幅優先探索の特性を活かして、探索する範囲を操作回数ごとに決めていきます。

bfs関数を呼び出すまでは基本的な幅優先探索と同じように普通に入力を受け取りました。
基本的な幅優先探索は次の記事で記載しています。
ebisuke33.hatenablog.com

bfs関数では最初に黒マスを全探索し、すべてキューに入れてしまいます。

このときキューに入っている要素が1回目の操作で探索する範囲です。

while文で幅優先探索を進めますが、len関数を用いてキューに入っている要素数だけ探索するようにしました。

例えば、while文の1回目のループでは、ループ前に全探索してキューに入っている黒マスが探索対象となります。

その探索中にキューに追加されていきますが、新しく追加された分は次回に探索することになります。

1回目のwhileを抜けると操作回数resに1を足します。

同じように2回目の操作対象は、2回目の探索時点でキューに入っている黒マスを探索し、新しくキューに追加された分は3回目に探索する、という処理を繰り返します。

最後はすべて黒マスに変わりますので、while文をbreakしてループを抜けます。

ループを抜けた後にresを出力すれば、求める操作回数となりACでした。

操作回数ごとの処理を実現するために、処理開始時点のキューの長さを覚えておくことがポイントでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

【AtCoder版！蟻本】ABC 088 D - Grid Repainting【幅優先探索】

AtCoder版！蟻本の幅優先探索で類題としてあげられているABC088 DをPythonで解いていきます。

リンク

atcoder.jp

AtCoder Beginner Contest 088 D - Grid Repainting

問題文

縦 H マス, 横 W マスに広がるマス目があり, 各マスは白または黒で塗られている. 上から i 番目で左から j 番目のマスを (i,j) で表す. すぬけ君は, このマス目を使って次のようなゲームをしたい. ゲームの開始時点ではマス (1,1) にゲームキャラクター「けぬす君」がいる. プレイヤーはけぬす君を上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す. けぬす君が白いマスだけを通って (H,W) にたどり着けばゲームクリアとなる.
ゲームを開始する前に, すぬけ君はいくつかの白いマス目の色を黒に変えることができる. ただし, マス (1,1) と (H,W) の色を変えることはできず, ゲームを開始するまでにすべての色の変更を行わなければならない.
ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる. そのとき, すぬけ君が取る可能性のある最大のスコアを求めなさい.ただし, すぬけ君がどのようにマス目の色を変えてもけぬす君が (H,W) にたどり着くことが出来ない場合、−1 と出力しなさい.
ただし, 各マスの色の情報は文字 si,j として与えられる. マス (i,j) が最初白で塗られている場合 si,j は . であり, マス (i,j) が最初黒で塗られている場合 si,j は # である.

制約

・H は 2 以上 50 以下の整数
・W は 2 以上 50 以下の整数
・si,j は . または # (1≤i≤H,1≤j≤W)
・s1,1, sH,W は . である

解答例

from collections import deque

# 入力
h, w = map(int,input().split())

maze = [] # 迷路の文字配列
for _ in range(h):
    maze.append(input())

# 各座標への最短距離の配列（INFで初期化）
INF = int(1e9)
D = [[INF] * w for i in range(h)]

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# スタート地点
sy = 0
sx = 0
# ゴール地点
gy = h-1
gx = w-1


# スタートからゴールへの最短距離を求める
def bfs():
    que = deque()
    que.append([sy,sx]) # スタート地点をキューに入れる
    D[sy][sx] = 0 # スタート地点の距離を0とする

    # キューが空になるまで探索
    while len(que) != 0:
        p = que.popleft() # 先入れのキューの要素を取り出す
        if p[0] == gy and p[1] == gx: # ゴールなら探索終了
            break
        for i in range(4): # pから4方向に移動 移動後の点は(nx,ny)
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            # 移動可能か、訪れたことがあるかの判定
            if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "#" and D[ny][nx] == INF:
                # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する
                que.append([ny,nx])
                D[ny][nx] = D[p[0]][p[1]] + 1
    return D[gy][gx]

# 最初黒色のマスの数
def black_count():
    black_num = 0 # 黒色のマス目の数
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "#":
                black_num += 1
    return black_num

tmp = bfs()
num = black_count()
if tmp == INF:
    print(-1)
else:
    res = h * w - tmp - num - 1
    print(res)

解説

縦 H マス, 横 W マスのマス目が白色か黒色で塗られていて、マス (1,1) からスタートし白色のマスだけを通ってマス (H,W)を目指します。
スタート前に白色のマスを黒色に変えることができ、塗り替えたマス目の数に応じて得点がもらえます。
このルールで最大何点をとることができるか、あるいはゴールにたどり着けないか 答える問題です。

初期状態のまま幅優先探索BFSでスタートからゴールへの最短経路を求めます。
この最短経路以外のマス目は黒に塗り替えても通らないで済むので、これを元に黒に塗り替える最大のマス目を解答する方針です。

幅優先探索は特に工夫しておらず、問題文から求まるスタート地点とゴール地点を代入して最短経路を求めます。
基本的な幅優先探索は次の記事で記載しました。
ebisuke33.hatenablog.com

次に初期状態の黒色のマス目を数えます。
black_count関数を作り、単純に全探索して黒色のマス目を数えます。

このふたつが求まれば、黒色に塗り替えることのできるマス目の最大値resは、H×Wのマス目から 最短経路と もともと黒色のマス目の数＋1を引いた値になります。
もし、スタートからゴールにたどり着けないときはBFSでINFが返ってくるので、-1を出力し、それ以外のときはresを出力すればOKです。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク